Sorting lists is a common operation in a range of programs.
Consider this example: A teacher wants to learn more about how well their students did in their most recent test. A teacher may want to sort the students’ scores in ascending and descending order so they can find out what the highest and lowest test scores were.
Enter, the selection sort. The selection sort is an algorithm that you can use to sort a list in either ascending order or descending order.
In this guide, we’re going to discuss how to write a selection sort program in Python. We’ll walk through an example throughout this guide so that you can learn the ins-and-outs of selection sorts.
What is a Python Selection Sort?
A selection sort algorithm sorts an array, which is a structure of data. A selection sort repeatedly finds the minimum element in a list and moves that element to the beginning of the list. This keeps going until the array is sorted in order.
Selection sorts assume that the first element in a list is the smallest value. The sort will then compare that value with the second element. If the second element is smaller than the minimum value, the second element becomes the minimum value.
This process is repeated until the last element of the list is reached. Once this element is reached, the minimum value is placed at the start of the unsorted list.
When Should You Use a Selection Sort?
Selection sorts, like bubble sorts, are best used for smaller lists. This is because the algorithm isn’t as efficient as others such as an insertion sort when used on larger lists.
A selection sort is a great sort to learn when you’re just starting with sorting algorithms. Other sorts can be difficult to master, but having a clear understanding of selection sorts can help you understand different types of lists.
Selection Sort Guide
There’s no better way to learn about selection sorts than to run through an example. Let’s go through and sort a list of student grades in ascending order. Consider this unsorted list:
We’ll start by calling the first value of our list the
minimum. We’ll be using this number throughout our algorithm to find the smallest number to move to the start of our list.
Next, we’ll compare the minimum value with the second element. If this element is smaller than minimum, the second element should become the minimum value.
In this case, we are going to compare 73 and 62. 73 is greater than 62, which means that our new minimum value is 62. Our list will then go through all the other numbers in our list:
- Is 61 greater than 62 (our minimum value)? No, so swap the numbers. Minimum becomes 61.
- Is 69 greater than 61 (our minimum value)? Yes, so do nothing. Minimum stays at 61.
Our list looks the same:
When you reach the end of the list, you can move minimum to the start of the list:
61 (our minimum value) has been moved to the start of the list, and every other value has moved up by one. We’ll repeat this process until all the elements are sorted.
Each iteration of our list will return the following:
- 73, 62, 61, 69
- 61, 73, 62, 69
- 61, 62, 73, 69
- 61, 62, 69, 73
When the selection sort has checked all the elements in the list, the sort will stop.
How to Perform a Selection Sort in Python
You’re now familiar with the theory: well done! It’s time for the big challenge. We’re going to implement the selection sort algorithm in Python. Let’s write a Python program that takes in an array and sorts it in ascending order.
We’ll start by defining a function that performs our selection sort:
def sortList(array): length = len(array) for item in range(length): minimum = item for i in range(item + 1, length): if array[i] < array[minimum]: minimum = i (array[item], array[minimum]) = (array[minimum], array[item])
We’ve started by using the len() method to get the length of our list. We then use this to initiate a for loop which loops over every item in our list.
For each iteration in the loop, we set the value of
minimum to be the first item in our list, like we did in our walkthrough earlier. Once we’ve set a minimum value, another for loop begins which runs through every item in our list.
For each item in the list, our algorithm checks if the minimum value is larger than that item. If it is, nothing happens; otherwise, the minimum value becomes the item that the program is reading.
Upon looping through every item in our list, our algorithm moves the minimum value to the start of the list. Then, our program will keep going until the top
for loop terminates. This is because selection sorts run a number of times equal to the length of a list.
You may have noticed that if we run our program, nothing happens. This is because we have not yet told our code what values to use yet. Add the following code to the bottom of your program, outside of the sortList function:
numbers = [73, 62, 61, 69] sortList(numbers) print("Sorted list:", numbers)
When we run our program, the following is returned:
Sorted list: [61, 62, 69, 73]
Our list has been sorted. Pat yourself on the back; you did it!
Selection sorts can be used to sort a list in descending order. If you want to sort a list in this way, you can change the “if” statement in the selection sort to the following:
if array[i] > array[minimum]:
We’ve changed the lesser than sign to a greater than sign. This will sort our list in descending order, because the minimum value will be set to the highest value in the list. Technically, our
minimum value becomes a
Selection sorts are an important method of sorting data. Selection sorts read through every item in a list and, on each iteration, move the smallest item to the start of the list. This happens until every item in the list has been read.
Selection sorts are not widely used outside of teaching because there are more efficient algorithms to use. With that said, they are a good springboard into learning other sorts, such as an insertion or merge sort.
Now you’re equipped with the knowledge – and code – you need to write a selection sort!