Selection Sort Algorithm

Selection Sort is a comparison-based sorting algorithm that selects and moves the smallest element from the input set to its correct position.

At the end of each iteration, the smallest element from the remaining elements is moved to its correct position, thus dividing the input into two partitions - one sorted and the set of remaining elements.

Consider the following input: [3,5,1,9,8,7] and let’s try to trace the selection sort steps on this input:

First Pass

1. [3,5,1,9,8,7]: no change as 3 and 5 are in the correct order.
2. [1,5,3,9,8,7]: 3 and 1 are swapped to ensure the correct order.
3. [1,5,3,9,8,7]: no change as 1 and 9 are in the correct order.
4. [1,5,3,9,8,7]: no change as 1 and 8 are in the correct order.
5. [1,5,3,9,8,7]: no change as 1 and 7 are in the correct order.

After the first iteration, the smallest element (1) is at its correct position. Similarly, after the second iteration and so-on:

1. Second Pass: [1,3,5,9,8,7] - 3 is at its correct position.
2. Third Pass: [1,3,5,9,8,7] - 5 is at its correct position.
3. Fourth Pass: [1,3,5,7,9,8] - 7 is at its correct position.
4. Fifth Pass: [1,3,5,7,8,9] - 8 is at its correct position.

A java based implementation of the algorithm is as follows:

public void sort(int[] input){
    int length = input.length;
    // as every element is compared with all the elements to its right
    // we only need to go till second last element via index "i" as for
    // "i" pointing to second last element (i < length -1), j will point
    // to last element (j < length)
    for(int i = 0; i < length - 1; i++){
        for(int j = i + 1; j < length; j++){
            // if out of place, then swap
            if(input[i] > input[j]){
                int temp = input[i];
                input[i] = input[j];
                input[j] = temp;
            }
        }
    }
}

Similar to bubble sort algorithm, the overall complexity of this algorithm is \(O(n^2)\).