Selection Sort in Python: Explained with Examples

Selection sort in Python is an in-place sorting algorithm. In this sorting algorithm, only one swap happens for every pass through the list. The algorithm works by recursively going through the input array. Each time of recursion returns an item that is smallest in the unsorted sequence and places it in the original array. 

Working of Selection Sort

The selection sort in Python is an enhanced version of bubble sort. However, for every iteration through the list, only one item is swapped. As the selection sort initiates an iteration, it looks for the largest value in the unsorted list and returns it to the proper location. Hence, after the first iteration, the largest value is in its place, the second iteration puts the second largest value in its place and so on. The process continues till all the items are returned to its location. (n – 1) iterations are required to sort an input array with ‘n’ items. This is because the final item should be in its place after the (n-1)th pass. 

Check out our free courses to get an edge over the competition.

An Example of Selection Sort

def selection _sort(L):

for i in range(len(L) – 1):

min_index = argmin(L[i:])

L[i], L[min_index] = L[min_index], L[i]

 Python Code Example for Selection Sort

The minimum value index is returned by the function argmin( ) in the pseudocode shown in Figure 1. A variable ‘I’ is used to track the position of the end of sorted list and the start of unsorted list. Every item in the unsorted sub list is more than any item in the sorted sublist always because the selection sort algorithm starts with zero items in the sorted sub list. 

First statement of the code raises the variable’s value by 1 (i + 1). The index of minimum value is determined by the second statement of the code. The third statement performs the swapping of the values. No temporary variables are required for the swapping because the value of the right-hand side is calculated by Python before it is assigned to the left-hand side.

Learn Software Development Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs or Masters Programs to fast-track your career.

Let us take an example of the unsorted list shown below to understand how the code in Figure 1 works. 

[9, 10, 8, 3, 4]

The sorting algorithm starts with zero items in the unsorted list. 

• 9, 10, 8, 3, 4

All the items are now placed in the unsorted list. The code looks through each item in the unsorted list to determine the least value. The least value in the list is 3 and it is swapped with 9 in the list. 

• 3, 9, 10, 8, 4

Now the remaining unsorted elements are compared with each other to find the next lowest element. The lowest element in the remaining items of the unsorted list is 4. It is swapped with 9. Now, the elements in the sorted list are 3, 4.

• 3, 4, 9, 10, 8

The process continues till all the elements of the unsorted list are sorted. 

• 3, 4, 8, 9, 10
• 3, 4, 8, 9, 10
• 3, 4, 8, 9, 10

Unique Features of Selection Sort in Python

• Selection sort is usually used to check whether all the items of the list are sorted or not.
• Selection sort swaps non-adjacent elements and hence, it is not a stable algorithm.
• The time complexity of selection sort is O (n2) where ‘n’ is the size of the list or the number of elements in the list.
• As it requires no additional memory, the space complexity of this algorithm is 1.

Merits of Selection Sort

This sorting algorithm is simpler and has more performance benefits in cases where auxiliary memory is limited. The major benefit of selection sort is that it performs well with a small list of items. No additional storage is required apart from the one that stores the original list because it is an in-place sorting algorithm. 

Check out upGrad’s  Advanced Certificate Programme in Cyber Security from IIIT Bangalore

Drawbacks of Selection Sort

The selection sort in Python is less efficient when executed on a huge list of items. The number of steps required for selection sort is in geometric progression. Hence, its performance worsens with the increase in the length of the list. The performance of bubble sorting algorithm is affected by the initial arrangement of items in the input array before the initiation of the sorting process. Therefore, only a list of a few items that are arranged randomly can give accurate results with the selection sort algorithm.

At upGrad, our Executive Post Graduate Programme in Software Development – Specialisation Cloud Backend Development, offered in collaboration with IIITB, is a 12-15 months program aimed at both freshers and experienced professionals wanting to understand cloud computing in more detail. The course is highly training-oriented and gives you all the practical exposure you require to get started in the world of software development and cloud computing. Check out the course page and get yourself enrolled soon!