Sorting Algorithms: Selection Sort

Selection Sort  |  Running time O(n²)  and Memory O(1)

This algorithm works as follows: find the smallest (or largest) element using a linear scan and move it to the front. Then find the next smallest (or next largest) element, and move it, and so on.    

If we have to sort an array of n elements,

- This algorithm makes n-1 passes of the array

- In every pass, it finds (selects) the smallest (or largest) element in the unsorted part of array, and moves it to the front.

Algorithm

//selection sort in descending order i.e. largest to smallest

for ( i=0; i< n-1; i++ )     //i controls the number of passes

{    int index=i;

/* Find the largest element */

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

     {    if( a[j] > a[index])   //use < to change sort order

          {    index = j;

          }

     }

    

     /* Move this element to the front (swapping) */

     temp      = a[i];

     a[i]      = a[index];

     a[index] = temp;

} 

Example: We will sort an array in descending order using selection sort.

Selection sort is the easiest sorting technique. Also, since each pass requires a maximum of one swap, there will be a maximum of n swaps during the sorting. Therefore, it is a better technique than bubble sort. However, a time complexity of O(n²) makes it an inefficient technique for large lists.