Algorithm: Selection sort, how it works and implementation in python

#algorithms #codenewbie #python #beginners

In this blog, I will talk about how selection sort works. I will implement examples in python3.

Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and placed that element at the beginning of the unsorted list.

How does Selection sort work?

The word ‘select’ means carefully chosen from a group of things as being the best or most valuable. If I have a list of numbers and, I pick a random number without any thinking this should not be select. Rather, If I thoughtfully pick the best one or the appropriate one it should be selected.

In the selection sort, every time we pick the appropriate elements from an array then put it on an appropriate position. Then applying this technique on the rest of the elements of the list, we will get our sorted array.

Let, we have five numbers 10, 5, 2, 8, 7 and we need to sort those numbers in ascending order. To do that use the selection sort algorithm. (fig-1)

Step-1: First we need to find the smallest number from the list of numbers. In this case, the number is 2. Now bringing 2 in the first position of the list. Then exchange 2’s old position with 10 (10 was in the first position). After this step, our list looks like this. (fig-2)

Step-2: Now we have the smallest number at the beginning of the list. So, now we find out the smallest number from the rest of the four numbers. That is 5. Here 5 is it’s the correct position. That’s why no need to swapping. (fig-3)

Step-3: In this step, we find out the smallest number among 10, 8, 7. Here 7 is the smallest. Now bringing 7 in the first among these three numbers. And swapping position with 10. Now our list looks like- 2, 5, 7, 8, 10, and we know that the first three numbers in the correct position. (fig-4)

Step-4: Now find the smallest between 8 and 10. Here 8 is the smallest one and it is in the correct position. So, there is no need to exchange positions. (fig-5)

Within 5 numbers 4 of those are sorted. So, the last one is naturally in the right position. Finally, our list is fully sorted. (fig-6)

Selection sort algorithm in detail:

Input: A list L has n number of elements.

Step-1: Let i = 0

Step-2: If i is greater or equal to (n-1); go to step 11.

Step-3: Let, the index of the smallest elements of the list is, index_min = i

Step-4: Let, j = i+1

Step-5: If j is greater or equal to n then go to step 9

Step-6: If L[j] < L[index_min] go to next step else go to step 8.

Step-7: index_min = j

Step-8: increment j by 1 then go to step 5.

Step-9: If i and index_min is not equal then swap the value of L[i] and L[index_min]

Step-10: Increment i by 1

Step-11: List is now sorted by ascending order.

Implementation in Python 3

def selection_sort(L):
    n = len(L)

    for i in range(0, n-1):
        index_min = i

        for j in range(i+1, n):
            if L[j] < L[index_min]:
                index_min = j

        if index_min != i:
            L[i], L[index_min] = L[index_min], L[i]


if __name__ == "__main__":
    L = [10, 5, 2, 8, 7]
    print("Before sort:", L)
    selection_sort(L)
    print("After sort:", L)

This blog previously published on medium.com