Selection Sort:
The selection sort improves on the bubble sort by reducing the number of swaps necessary from O(N^2) to O(N) .Unfortunately the number of comparisons remains O(N^2) .
Brief Description:
What involved in the selection sort is making a pass through all the players and picking the shortest one.This shortest player is then swapped with the player o the left end of the line,at position 0.now the left most player is sorted and wont need to be moved again.Notice in this algorithm the sorted players accumulate on the left,whereas in the bubble sort they accumulated on the right.
Selection Sort Workshop:
/**
*
*/
/**
* @author Abhinaw.Tripathi
*
*/
class ArraySel
{
private long[] a;
private int nElems;
public ArraySel(int max)
{
a=new long[max];
nElems=0;
}
public void insert(long value)
{
a[nElems]=value;
nElems++;
}
public void display()
{
for(int j=0;j<nElems;j++)
System.out.println(a[j] + " ");
System.out.println(" ");
}
public void selectionSort()
{
int min,in,out;
for(out=0;out<nElems;out++)
{
min=out;
for(in=out+1;in<nElems;in++)
{
if(a[in] < a[min])
min=in;
swap(out,min);
}
}
}
private void swap(int one, int two)
{
long temp=a[one];
a[one]=a[two];
a[two]=temp;
}
}
public class SelectionSortTest {
/**
*
*/
public SelectionSortTest() {
// TODO Auto-generated constructor stub
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
ArraySel arr=new ArraySel(100);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.display(); // before sort
arr.selectionSort();
arr.display(); //after sort
}
}
Complexity of Selection Sort:
It performs the same number of comparisons as the bubble sort: N*(N-1)/2 .
So Selection sort runs in O(N^2) .