selection sort

Selection Sort: This algorithm is based on the idea of finding the minimum or maximum element in the unsorted array and then putting it in its correct position for a sorted array.

We have an array A [ ] = {7, 5, 4, 2} and we need to sort it in ascending order.

Let’s find the minimum element in the array i.e., 2 and then replace it with the first position's element, i.e., 7. Now we find the second largest element in the remaining unsorted array and put it at the second position and so on.

Complexity : Here as to find the minimum element from the array of n elements, we require n-1 comparisons to be performed. Then, after putting minimum element to its proper position, size of unsorted array reduces to n-1and then n-2 comparisons are required to find the minimum in the unsorted array. Therefore (n-1) + (n-2 ) + .......+ 1 = ( n * (n-1) ) / 2 comparisons and n exchanges (swapping ), which gives the complexity of O( n² ).

import java.util.Scanner;

class Selection

{

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

int arr[]=new int[n];

void input()

{

for(int i=0;i<n;i++)

{

System.out.printf("enter the value of %d element",(i+1));

arr[i]=sc.nextInt();

}

}

void display()

{

System.out.println();

System.out.println("the sorted array is:");

for(int i=0;i<n;i++)

System.out.print(arr[i]+"\t");

}

void sort()

{

int minimum=0;

for(int i=0;i<n-1;i++)

{

minimum=i;

for(int j=i+1;j<n;j++)

{

if(arr[j]<arr[minimum])

{

minimum=j;

}

int temp=arr[i];

arr[i]=arr[minimum];

arr[minimum]=temp;

}

}

}

void showSteps()

{

int minimum=0;

for(int i=0;i<n-1;i++)

{

minimum=i;

System.out.println();

System.out.printf("outer loop i=%d\t",i);

for(int j=i+1;j<n;j++)

{

if(arr[j]<arr[minimum])

{

minimum=j;

}

}

int temp=arr[i];

arr[i]=arr[minimum];

arr[minimum]=temp;

try

{

Thread.sleep(2000);

}

catch(InterruptedException e)

{

System.out.println(e.getMessage());

}

for(int k=0;k<n;k++)

System.out.print(arr[k]+"\t");

}

}

}

class SelectionTest

{

public static void main(String args[])

{

System.out.println("enter the value of total number of elements:");

Selection s1=new Selection();

s1.input();

//s1.sort();

//s1.display();

s1.showSteps();

s1.display();

}

}