Selection sort

In this sort, we basically compare 1st element in an array with every other element and replace the 1st element with the smallest element found in the whole array. If there is no smaller element found, we leave the 1st element as it is and move on to the next element and again perform the same steps.

Selection Sort:-

In selection sort, we basically starts from left to right and keep a pointer on smallest element as the first element.
As we traverse from left to right, we compare every element with the pointer and swap the position if pointer element>current elemement.
In next round, we again start from left to right and starting point this time becomes leftmost element +1

public void selectionSort()
{
int out, in, min;
for(out=0; out<nElems-1; out++) // outer loop
{
min = out; // minimum
for(in=out+1; in<nElems; in++) // inner loop
if(a[in] < a[min] ) // if min greater,
min = in; // we have a new min
swap(out, min); // swap them
} // end for(out)
} // end selectionSort()

Efficiency :- O(N2) as there are two loops but unlike bubble sort, this is much fast as there are less swaps involved.

Invariant:- In the selectSort.java program, the data items with indices less than or equal to out
are always sorted.