Prerequisites

To learn about Selection Sort, you must know:

1. Python 3
2. 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 the 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. 

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

1. Consider the first element to be sorted and the rest to be unsorted
2. Assume the first element to be the smallest element.
3. Check if the first element is smaller than each of the other elements:
   1. If yes, do nothing
   2. If no, choose the other smaller element as minimum and repeat step 3
4. After completion of one iteration through the list, swap the smallest element with the first element of the list.
5. 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!