In this tutorial, you will learn how the selection sort algorithm
. Also, you will find working examples of selection sort in Python
.
Introduction to Selection Sort Algorithm
Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.
How the Selection Sort Algorithm?
 Set the first element as
minimum
.  Compare
minimum
with the second element. If the second element is smaller thanminimum
, assign the second element asminimum
. Compareminimum
with the third element. Again, if the third element is smaller, then assignminimum
to the third element otherwise do nothing. The process goes on until the last element.  After each iteration,
minimum
is placed in the front of the unsorted list.  For each iteration, indexing starts from the first unsorted element. Steps 1 to 3 are repeated until all the elements are placed at their correct positions.
Selection Sort Algorithm
1 2 3 4 5 6 7 8 9 10 
selectionSort(array, size) repeat (size  1) times set the first unsorted element as the minimum for each of the unsorted elements if element < currentMinimum set element as new minimum swap minimum with first unsorted position end selectionSort 
Python Examples
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
# Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change > to < in this line # select the minimum element in each loop if array[i] < array[min_idx]: min_idx = i # put min at the correct position (array[step], array[min_idx]) = (array[min_idx], array[step]) data = [2, 45, 0, 11, 9] size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data) 
Complexity
Cycle  Number of Comparisons 

1st  (n1) 
2nd  (n2) 
3rd  (n3) 
…  … 
last  1 
Number of comparisons: (n – 1) + (n – 2) + (n – 3) + ….. + 1 = n(n – 1) / 2 nearly equals to n^{2}.
Complexity = O(n^{2})
Also, we can analyze the complexity by simply observing the number of loops. There are 2 loops so the complexity is n*n = n^{2}.
Time Complexities:

 Worst Case Complexity: O(n^{2}) If we want to sort in ascending order and the array is in descending order then, the worst case occurs.
 Best Case Complexity: O(n^{2}) It occurs when the array is already sorted.
 Average Case Complexity: O(n^{2}) It occurs when the elements of the array are in jumbled order (neither ascending nor descending).
The time complexity of the selection sort is the same in all cases. At every step, you have to find the minimum element and put it in the right place. The minimum element is not known until the end of the array is not reached.
Space Complexity:
Space complexity is O(1) because an extra variable temp is used.
Selection Sort Applications
The selection sort is used when:
 a small list is to be sorted
 cost of swapping does not matter
 checking of all the elements is compulsory
 cost of writing to memory matters like in flash memory (number of writes/swaps is O(n) as compared to O(n^{2}) of bubble sort)
The article was published on November 29, 2020 @ 4:25 PM
Leave a Comment