Selection sort

Selection sort is a simple algorithm which will be applicable to sort the small lists or mostly sorted lists. Selection sort would sort by finding the minimum (in case of ascending) or maximum (in case of descending) value and swap that with the first element of the list.
Name selection is called because, it selects an intended element to be swapped with the first element.

Algorithm

START
DECLARE n, list, min
ACCEPT n
ACCEPT n values into an array list
FOR EACH i IN 0 to n-1
LOOP
min := i;
FOR EACH j IN i+1 to n-1
LOOP
IF list[j] < list[min] THEN
min := j;
END IF
END LOOP
IF i <> min THEN
temp := list[i];
list[i] := list[min];
list[min]:= temp;
END IF
END LOOP
END

Java program


import java.io.*;

/**
* This class demonstrates the bubble sort.
* @author SANTHOSH REDDY MANDADI
* @version 1.0
* @since 10 September 2009
*/
public class SelectionSort
{
public static void main(String[] args) throws Exception
{
int values[]=new int[5];
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter "+values.length+" values to sort using bubble sort");
for(int i=0;i<values.length;i++)
{
try{
values[i]=Integer.parseInt(br.readLine());
}catch(NumberFormatException e)
{
e.printStackTrace();
values[i]=0;
}
}
selectionSort(values);
for(int i=0;i<values.length;i++)
{
System.out.print(values[i]+" ");
}
}

/**
* This method will sort the passed array
* @author SANTHOSH REDDY MANDADI
* @since 10-Sep-2009
* @param an array of the list of values to be sorted
*/
public static void selectionSort(int[] values)
{
//Iterating the list till the end of the list except last one
for (int i=0; i<values.length-1;i++)
{
//Considering the minumum value is current iteration array element
int min = i;
//Trying to find out the smallest element in the array
for(int j=i+1; j<values.length;j++)
{
if (values[j]<values[min])
{
min = j;
}
}
//If smallest element found other than the current iteration array element, swapping will happen
if (i != min)
{
int swap = values[i];
values[i] = values[min];
values[min] = swap;
}
}
}
}

Explanation


Let us consider we've executed the above program by inputting the values (53, 24, 31, 64, 3). Here is how the list will be modified in each iteration.
Iteration - list values
First - 3 24 31 64 53
Second - 3 24 31 64 53
Third - 3 24 31 64 53
Fourth - 3 24 31 53 64
Fifth - 3 24 31 53 64
Above program has been tested in JDK 1.4, 1.5, and 1.6.
Click here to check out other programs that I've developed.