Sorting the data is very important for indexing and searching. A lot of sorting algorithms have been developed so far to meet the current needs of speed. One such algorithm that appeared initially for addressing the sorting problem is Selection Sort.
Like Insertion Sort, Selection Sort tends to be very slow. Both have time Big-O of
n is the number of entries to be sorted. Both of these algorithms require a lot of computation in comparisons, and in swapping.
Selection Sort works on the principle of comparing and swapping for arranging the elements. Unlike Insertion Sort, which compares adjacent entries, this algorithm selects the smallest or largest values (depending on sorting order) in a subset of the list and moves it to the front of the subset. This shifting is done by swapping the smallest or largest value with that at the front. After one element is placed at the front spot, we can say that this element is
sorted. So, this element is ignored for next iteration. In a nutshell, during each iteration the subset is of size
N - n, where
n is the number of sorted elements in the list of
In this example, I’ll be sorting data in ascending order. For this, I’ll select the smallest value and move it to the front of the subset.
Alternatively, one can select the largest value and move it to the back of the subset. In this case, the list will be sorted from right. Ultimately, both methods yield the same result.
Say we have a list of 5 values:
[8, 2, 3, 9, 4];
N = 5
n = 0
Subset = (8, 2, 3, 9, 4)
Smallest = 2
Front = 8, hence 2 and 8 are swapped
[2, | 8, 3, 9, 4]
n = 1
Subset = (8, 3, 9, 4)
Smallest = 3
Front = 8, hence 3 and 8 are swapped
[2, 3, | 8, 9, 4]
n = 2
Subset = (8, 9, 4)
Smallest = 4
Front = 8, hence 4 and 8 are swapped
[2, 3, 4, | 8, 9]
n = 3
Subset = (8, 9)
Smallest = 8
Front = 8, no swap
[2, 3, 4, 8, | 9]
n = 4
Now that only one element is left, we can assume it to be sorted automatically.
[2, 3, 4, 8, 9]
This function takes a list of values and
returns a sorted list.
def select_sort( values ): n = len( values ) # no of elements index = 0 # location of smallest value for i in range( n - 1): # as the last element will already be sorted smallest = values[i] for j in range(i, n): if values[j] < smallest: index = j # index of current smallest value # move the smallest to the front of subset i.e., swap values[index], values[i] = values[i], values[index] return values