In this post I will implement another well know sorting algorithm – Selection Sort. The idea of the algorithm is quite simple:

• divide input list into two parts: sorted (built up from left to right) and unsorted (remaining items to be sorted)
• initially sorted part is empty and unsorted part contains input list
• starting from the beginning of the unsorted part find the smallest element in the list
• swap its position with the left most element in the unsorted part
• after each iteration move sorted / unsorted boundary by one element to the right

We can visualize selection sort algorithm by sorting following list [5 1 4 2 8]. I’ll use colors to specify currently smallest unsorted element, current unsorted element and already sorted elements.

Iteration #1 : [5 1 4 2 8] [5 1 4 2 8] → [5 1 4 2 8] → [5 1 4 2 8] → [5 1 4 2 8] → [5 1 4 2 8] → [5 1 4 2 8] → [1 5 4 2 8]

Iteration #2 : [1 5 4 2 8] [1 5 4 2 8] → [1 5 4 2 8] → [1 5 4 2 8] → [1 5 4 2 8] → [1 5 4 2 8] → [1 2 4 5 8]

Iteration #3 : [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8] → [1 2 4 5 8] → [1 2 4 5 8]

Iteration #4 : [1 2 4 5 8] [1 2 4 5 8] → [1 2 4 5 8] → [1 2 4 5 8]

Iteration #5 : [1 2 4 5 8]

Implementation of the selection sort is quit simple:

As with bubble sort we have two loops: outer and inner. Outer loop is executed for each element (n times) and inner loop is executed for n/2 elements on average. As a result we have O(n²/2) or just O(n²) complexity.

Complexity: O(n²).