- Loop through the array
- Find the smallest element in the unsorted portion of the array
- Swap the smallest element with the first element in the unsorted portion of the array
The sorted portion of the array is on the left side while the unsorted portion is on the right. In the diagrams below, the blue boxes represent the sorted elements of the array, while the white boxes represent the unsorted elements. Elements that are going to be swapped are shown in green boxes.
On every iteration, an element from the unsorted portion is added to the sorted portion. For example, if we start with this array:
At this stage, the unsorted array is the entire array. The smallest element found is
1, so swap that with the first element of the unsorted array.
So after the first iteration, only the first element is sorted:
Now loop through the unsorted array (the items after the first element, which is now sorted). In the unsorted array, swap the smallest item with the first item
After the second iteration, the first two elements are sorted, as another element from the unsorted portion is added to the sorted portion:
n - 1 times, where
n is the length of the list.
Note that it runs
n - 1 times, since the last element is already sorted.
function selection_sort(list): n = list.length for i from 0 to n-1: # Initialize smallest element to first one smallest_index = 1 # Traverse through the unsorted list to find the # smallest element for j from i to n: if collection[j] < collection[smallest_index]: smallest_index = j # Swap smallest element with first element of # unsorted list swap(collection[smallest_index], collection[i]) return collection
While the pseudocode will produce expected results, there is a simple optimization we can make.
smallest_indexis already given an initial value of
i, so there is no need to start at
iin the inner for loop. Even if
ihappens to be the smallest value,
smallest_indexis already set to
- We only need to swap
iis not equal to
def selection_sort(collection): length = len(collection) for i in range(length - 1): smallest_index = i for j in range(i + 1, length): if collection[j] < collection[smallest_index]: smallest_index = j if smallest_index != i: collection[smallest_index], collection[i] = ( collection[i], collection[smallest_index], ) return collection
To debug, I am going to run the following and print the list at every iteration:
selection_sort([3, 5, 2, 1, 9, 6])
The output is
[3, 5, 2, 1, 9, 6] [1, 5, 2, 3, 9, 6] [1, 2, 5, 3, 9, 6] [1, 2, 3, 5, 9, 6] [1, 2, 3, 5, 9, 6] [1, 2, 3, 5, 6, 9] [1, 2, 3, 5, 6, 9]
The worst-case scenario is since there is a nested loop.
The first iteration has
n swaps, the second has
n - 1, the third has
n - 2, and so on, so
Since is the highest magnitude, the time complexity is .
The best case scenario is also since selection sort will not exit if the list is already sorted.