# Sorting: Selection Sort

Algorithms Sorting

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}/2) or just O(n^{2}) complexity.

**Complexity:** O(n^{2}).