Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Following examples explain the above steps:

From the below animation it can be seen that Selection sort takes the same time for sorting all types of input elements because none of the loops depend upon the data in the array. It has to scan all the elements to find the lowest element.

What are random, nearly sorted, reversed and few unique elements?

  1. Random: {6, 9, 5, 8, 7, 4, 2, 1, 3}
    Here all the elements are arranged in a random fashion.
  2. Nearly sorted: {5, 6, 7, 8, 9, 1, 2, 3, 4}
    The array is nearly sorted. For example, the above array if divided into two, are sorted individually.
  3. Reversed: {9, 8, 7, 6, 5, 4, 3, 2, 1}
    The array elements are reverse sorted and we are supported to sort them in ascending order.
  4. Few Unique: {1, 1, 2, 9, 4, 3, 2, 5, 9, 6}
    The array contains duplicate entries.
Random Nearly Sorted Reversed Few Unique

Algorithm

// One by one move boundary of unsorted subarray
For i = 1 to n-1 do
       // Find the minimum element in unsorted array
       min_idx = i
       For j = i + 1 to n-1 do
             If A(j) < A(min_idx) then
                    min_idx = j
             End-If
       End-For
       // Swap the found minimum element with the first element
       swap( A[min_idx], A[i])
End-For

Implementation

void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
    for (i = 0; i < n-1; i++)
    {
        min_idx = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min_idx])
            min_idx = j;
        swap(&arr[min_idx], &arr[i]);
    }
}

Analysis

Among simple average-case Θ(n2) algorithms, selection sort almost always outperforms bubble sort. Insertion sort is very similar in that after the kth iteration, the first k elements in the array are in sorted order. Insertion sort’s advantage is that it only scans as many elements as it needs in order to place the k + 1st element, while selection sort must scan all remaining elements to find the k + 1st element.

Simple calculation shows that insertion sort will therefore usually perform about half as many comparisons as selection sort, although it can perform just as many or far fewer depending on the order the array was in prior to sorting. It can be seen as an advantage for some real-time applications that selection sort will perform identically regardless of the order of the array, while insertion sort’s running time can vary considerably. However, this is more often an advantage for insertion sort in that it runs much more efficiently if the array is already sorted or “close to sorted.”

Auxiliary Space: O(1)
Sorting In Place: Yes
Stable: Yes

The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Source: Wikipedia