Prerequisites
To learn about Selection Sort, you must know:
- Python 3
- Python data structures – Lists
What is Selection Sort?
We are in the third tutorial of the sorting series. The previous tutorial talks about Bubble Sort and Insertion Sort. If you haven’t read that, please do as we will be building off of those concepts. Like all sorting algorithms, we consider a list to be sorted only if it is in ascending order. Descending order is considered the worst unsorted case.
Similar to Insertion Sort, we begin by considering the first element to be sorted and the rest to be unsorted. As the algorithm proceeds, the sorted portion of the list will grow and the unsorted portion will continue to shrink.
Selection Sort is about picking/selecting the smallest element from the list and placing it in the sorted portion of the list. Initially, the first element is considered the minimum and compared with other elements. During these comparisons, if a smaller element is found then that is considered the new minimum. After completion of one full round, the smallest element found is swapped with the first element. This process continues till all the elements are sorted.
- Bubble Sort: Quick Tutorial and Implementation Guide
- How to Sort Python Dictionaries by Key or Value
- Python Programming – List Functions And Methods
Let us see this using an example, alist = [5,9,1,2,7,0]
5 is considered sorted and the elements 9,1,2,7,0 are considered unsorted.
Round 1:
5 is the minimum 5<9: nothing happens 5>1: 1 is new minimum 1<2: nothing happens 1<7: nothing happens 1>0: 0 is the new minimum Swap 0 and 5 alist = [0,9,1,2,7,5]
Round 2:
9 is the minimum 9>1: 1 is the new minimum 1<2: nothing happens 1<7: nothing happens 1<5: nothing happens Swap 1 and 9 alist = [0,1,9,2,7,5]
Round 3:
9 is considered minimum 9>2: 2 is the new minimum 2<7: nothing happens 2<5: nothing happens Swap 2 and 9 alist = [0,1,2,9,7,5]
Round 4:
9 is considered minimum 9>7: 7 is the new minimum 7>5: 5 is the new minimum Swap 9 and 5 alist = [0.1.2.5,7,9]
Round 5:
7 is considered minimum 7<9: nothing happens alist = [0.1.2.5,7,9]
Note: even though after round 4 we can see the list is sorted, there is no way for the algorithm to know this. Hence only after completely traversing the entire list, the algorithm stops.
See this animation for better understanding.
How to implement Selection Sort?
Now that you have a fair understanding of what Selection Sort is, let us take a look at the algorithm and its code.
Algorithm
- Consider the first element to be sorted and the rest to be unsorted
- Assume the first element to be the smallest element.
- Check if the first element is smaller than each of the other elements:
- If yes, do nothing
- If no, choose the other smaller element as minimum and repeat step 3
- After completion of one iteration through the list, swap the smallest element with the first element of the list.
- Now consider the second element in the list to be the smallest and so on till all the elements in the list are covered.
NOTE: Once an element is added to the sorted portion of the list, it must never be touched and or compared.
Code
def selectionSort(alist):
for i in range(len(alist)):
# Find the minimum element in remaining
minPosition = i
for j in range(i+1, len(alist)):
if alist[minPosition] > alist[j]:
minPosition = j
# Swap the found minimum element with minPosition
temp = alist[i]
alist[i] = alist[minPosition]
alist[minPosition] = temp
return alist
print(selectionSort([5,2,1,9,0,4,6]))
Conclusion
Selection Sort works best with a small number of elements. The worst case runtime complexity of Insertion Sort is o(n2) similar to that of Insertion and Bubble Sort. That’s it for this tutorial. Happy Pythoning!
You can Also Check: