Selection Sort

The Selection Sort is intuitive algorithm where we select elements one by one and compare with others. The main approach of selection sort is to find the minimum element of the array and put it in the first position. There is the first element of the sorted subarray. Then, find the minimum element in the rest of the array (which is unsorted), and move it next to the sorted subarray as second one, and so on.

Each time, the next found element will be greater or equal than all elements in the sorted subarray, but less or equal than all elements in the unsorted subarray.

Example 1

Example 2: Step by Step

arr = [0, -4, 12, 4, 10, 4]

Find min element in subarray arr[0:] and place it to the beginning:

arr = [ -4, 0, 12, 4, 10, 4]

Find min element in subarray arr[1:] and place it at the end of sorted subarray:

arr = [-4, 0, 12, 4, 10, 4 ]

Find min element in subarray arr[2:] and place it at the end of sorted subarray:

arr = [-4, 0, 4, 12, 10, 4 ]

Find min element in subarray arr[3:] and place it to the end of sorted subarray:

arr = [-4, 0, 4, 4, 10, 12 ]

Find min element in subarray arr[4:] and place it at the end of sorted subarray:

arr = [-4, 0, 4, 4, 10, 12 ]

Unsorted subarray has only one element now, so we won’t replace it, the algorithm is over.

arr = [-4, 0, 4, 4, 10, 12]

Time complexity of the algorithm is O(N^2), where N is the length of array. That's because there are two nested loops in the algorithm. To be clear, the number of operations is N-1 + N-2 + … 2+1 = N(N-1)/2, which is O(N^2).

Space complexity: O(1).