In this article we are going to learn how to implement Selection Sort with Python. Selection Sort is a simple and intuitive sorting algorithm. It can be performed using an auxiliary array to store the results, or done in-place, meaning the original array is modified and no additional storage is required. Since the in-place version is not difficult to implement, and saves on storage requirements, this is the version you will usually see.
Take a look at this sequence of images to see how the auxiliary array version works. It is quite simple, and mimics the way many people would naturally approach sorting items like cards, books etc.
The steps are:
- Find the smallest value in the original list.
- Move this smallest value to the leftmost free position in the results array.
- Continue until all the values in the original list have been moved.
Finding the Minimum Value in a Python List
The implementation of Selection Sort relies upon another algorithm which is repeatedly used. This is the algorithm for finding the minimum value in a list. To understand how Selection Sort works, you will need to make sure you understand this component algorithm.
Note: Many languages, including Python, have a built in min() function, but when studying algorithms is is very useful to know how these kinds of procedures can be implemented from basic components.
Here are the steps for finding a minimum value.
- Create a variable called min_index and set it to the first position in the list (usually 0).
- Iterate through the list and if a value is greater than the one at min_index, update min_index to the new position.
This approach gives us the position or index of the minimum value, which is needed in Selection Sort. You could also work directly with the value itself. As a side-note, being ultra-clear about whether your are considering a value or a position (index) at any given stage in an algorithm can save a lot of confusion.
def find_min(xs): min_index = 0 for i in range(len(xs)): if xs[i] < xs[min_index]: min_index = i return xs[min_index]xs = [3, 2, 1, 5, 4]min_value = find_min(xs)print(f”The minimum value is {min_value}.”)
Pseudocode for Selection Sort
The steps for in-place Selection Sort are as follows:
- At any given stage there will be a sorted section and an unsorted section of the list.
- Initially the sorted section has length 0.
- Iterate through unsorted section to find the minimum value.
- Swap this minimum value with the first value of the unsorted section.
- The length of the sorted section has now increased by 1 and the length of the unsorted section has decreased by 1.
- Repeat until the sorted section is the same size as the original list.
The image shows the finding of the first minimum value (the 1 in green), then the swapping of the 1 with the 3 and finally the beginning of the next pass, with the sorted section in green and the unsorted section in red.
Here is a version that looks more like a real programming language:
(From Introduction to the design & analysis of algorithms / Anany Levitin.)
As an Amazon Associate I earn from qualifying purchases.
Selection Sort Python Implementation
Below is a Python implementation of in-place Selection Sort.
def selection_sort(xs): for i in range(len(xs) – 1): # Last value will automatically be in correct position. # Find minimum value in unsorted region. min_index = i for j in range(i + 1, len(xs)): # Update min_index if the value at j is lower than current minimum value. if xs[j] < xs[min_index]: min_index = j # After finding the minimum value in the unsorted region, swap with the first unsorted value. xs[i], xs[min_index] = xs[min_index], xs[i]xs = [3, 2, 1, 5, 4]print(xs)selection_sort(xs)print(xs)print(all(xs[i] <= xs[i + 1] for i in range(len(xs) – 1))) # A nice Pythonic way to check list is sorted.
This article has explored the Selection Sort algorithm and how to implement it with Python.
Happy computing!