Selection Sort

April 20, 2019 2 minutes

As with Bubble Sort, Selection Sort is another sorting algorithm that is based on the approach of compare and swap. It also has $O(n^2)$ complexity thus making it un-usable for very large datasets.

Selection Sort is based on the method of identifying the smallest (or largest, depending on the sorting requirement) element from the given input dataset and replacing it with the value at smallest not yet sorted index.

Consider the following example :

SelectionSort

For the given input array {10,8,11,7,21,4}, we start by moving the smallest element i.e. 4 to the lowest index by swapping it with value at index 0. In the next step, 8 is replaced with next smallest element which is 7, and then 11 with 8 and so-one until we have the entire array sorted.

From the above illustration, it can be clearly seen that the algorithm divides the input dataset into two parts or subsets. One of these subsets is always sorted and the other remains unsorted. Elements from the unsorted dataset are choosen and are appended to the sorted subset until the unsorted subset cease to exist.

Pseudo Code

  1. Initialize
    • length = number of input elements
    • i = start of array (lowest index)
    • j = i
  2. For every i from 0 to length
    • For every j from i to length
      • if element[i] > element[j]; swap these two
      • else, continue

Complexity

For a sequential dataset of size n, the number of comparisons to be performed, to find the minimum element is directly proportional to the number of elements n.So in the first step, it will take n-1 steps and then n-2 and then n-3 and so-on to find the minimum element. Assuming that the swapping operation can be performed in constant time, the overall complexity can be summarized in terms of these steps to identify the minimum value.

Mathematically speaking, the overall complexity can be described as :

$$(n-1) + (n-2) + (n-3) + \cdots + 1 = (n-1)\left(\frac{(n-1) + 1}{2}\right) \approx O(n^2)$$

Java Implementation

    /**
     * a method to demonstrate selection sort algorithm 
     * @param input the input array that needs to be sorted
     * @return sorted array
     */
    public int[] sort(int[] input) {
        int length = input.length;
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++) {
                if (input[i] > input[j]) {
                    int temp = input[i];
                    input[i] = input[j];
                    input[j] = temp;
                }
            }
        }
        return input;
   }

A working example of the algorithm with test cases can be found here

comments powered by Disqus