In this article, we will be discussing the Python Selection Sort Algorithm in complete detail. We will start with it’s explanation, followed by a complete solution which is then explained by breaking it down into steps and explaining each of them separately.
At the end we have also included a small comparison of the Python Selection Sort with others similar algorithms. As a bonus, we also have a video explanation of the Python Selection Sort Algorithm, which is included at the very end of the article.
Methodology
The Selection Sort Algorithm is one of the simpler Algorithms out there that you can use for sorting purposes. It uses a very simple logic pattern, which involves finding the minimum value of the items being sorted, and then moving it to the start of the of the list. In the next iteration, we narrow our range to exclude the first (now sorted) minimum value and proceed to locate the next minimum. We then place this minimum at the start of our search range, which means it’s after the first minimum value we found. This process continues till all values have been sorted.
Best Case Scenario: O(n2)
Worst Case Scenario: O(n2)
Selection Sort Algorithm (Code)
The code for the Selection Sort Algorithm is also fairly short and simple. It uses two nested for loops to iterate through the entire list. Think of the first for loop as the number of passes (times we iterate through the list) and the second for loop as the indexes of each element in the list.
def selection_sort(arr):
for i in range (0, len(arr) - 1):
minIndex = i
for j in range (i+1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
if minIndex != i:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
nums = [5,9,1,2,4,8,6,3,7]
selection_sort(nums)
print(nums)
The output of the above code, is a fully sorted list of numbers.
[1, 2, 3, 4, 5, 6, 7, 8, 9]You’ll notice that due to “i” increasing, the search range narrows as the number of passes increase. This is because as we sort the string, the unsorted part gets smaller and smaller, so we can reduce the search range to only include the unsorted part. This helps improve performance and increase the efficiency of the Python Selection Sort Algorithm.
for i in range (0, len(arr) - 1):
minIndex = i
In the above snippet, the minIndex = i line ensures that the first value of the search range is assigned as the min value. It doesn’t have to be the first index of the search range, as long as it is a value from the list of numbers.
for j in range (i+1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
The above snippet is the part responsible for locating the minimum value. We iterate through the loop from the second index (the first index is in minIndex) and compare them to minIndex. If any value is smaller than the value at minIndex, we assign that index to minIndex as the index of the new minimum value. Otherwise we leave minIndex as it is. This of course, means that minIndex itself turned out to be the smallest value.
Swapping
This part of the code is actually a small optimization trick as well as the swapping code. Instead of swapping indiscriminately, we only do the swap if the Index of the minimum value is actually different from the index “i”. This prevents us from swapping the min value with itself. This can occur if the minimum value turned out to be the one at the start of the list. (Remember that we, by default take the first element of the search range as the minimum value).
if minIndex != i:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
The swap occurs between index i, which is the start of the search range, and the minimum value. The minimum value is now at the start of the search range.
Selection Sort Explanation
In this section we will be completely solving a worked example, showing you the step by step process of the Selection Sort Algorithm.
Pictured above is the list of values we will be using.
The value is i that you can see to the side represents the “pass number”. It’s basically the first for loop in the code we discussed earlier. i = 0 means we are on the first pass.
The very first thing we do, is minIndex = i. What we are doing here basically, is making the first value of the search range the “minimum value”. We shall now iterate through the array, checking to see if there is any value smaller than 6.
9 is not smaller, hence we do nothing and move on.
1 is smaller than 6, hence we replace it as the new MinValue.
We continue onwards until we reach the end (1 was the smallest). Now we actually swap the minimum value, with the value at index i. The value index i is 6, and the minimum value is 1.
In the above image, you can see that both have been swapped. The value 1, is now at it’s correct position.
We will now begin the next pass. For visualization purposes, I am separating the 1 from the rest of the array. This is because the new search range from starts from 1, not 0. As such, the value 9 is picked the as the minimum value.
Proceeding forwards, gives us a new minValue 6.
New minimum value is 3.
New minimum value is 2.
We will now begin the swap and partition procedure, where 2 is swapped with the ith index value, which is 9.
1 and 2, are now part of the sorted part of the array, and are in their correct positions.
The third pass begins from the value 6, which we pick as our Min value.
The minimum value is located in the next index, of value 3.
There is no other smaller value, hence we end up at the end of the array. Swapping 3 with 6, gives us the above output.
We continue on in this manner, until the entire array has been sorted, and we are left with the below output.
Video Tutorial
Here we you can watch the video version of the Python Selection Sort Algorithm. If you are having trouble understanding, or still have some doubts, be sure to check this out. It’s a more interactive experience which will definitely help you.
This marks the end of the Python Selection Sort Algorithm Tutorial. Any suggestions or contributions for CodersLegacy are more than welcome. Questions regarding the tutorial content can be asked in the comments section below.