Selection Sort Python: A Guide

A Python selection sort divides a list into two small lists. One list represents the sorted elements. The other list contains the unsorted elements. The selection sort finds the smallest or highest values in each iteration and moves those values to the ordered list.

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. This will let them easily 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 Python selection sort repeatedly finds the minimum element in a list and moves that element to a particular end of the list. The sort keeps going until the array is sorted in order. You can also instruct a selection sort to find the maximum element. Both approaches sort a list.

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.

Python 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. Each iteration of the selection sort will find the smallest element and move it into the sorted subarray.

Sorting the minimum element is one option. A selection sort works if you sort the maximum element. But, we’re using the minimum element in this example.

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.

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:

1. 73, 62, 61, 69
2. 61, 73, 62, 69
3. 61, 62, 73, 69
4. 61, 62, 69, 73

When the selection sort has checked all the elements in the list, the sort will stop.

The sorted subarray and the subarray which is unsorted are both invisible to us. Our algorithm sorts an array for us and keeps track of the unsorted part of the array.

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 program that takes in a Python array and sorts it in ascending order.

Define a Sort Function

We’ll start by defining a Python 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 Python len() method to get the length of our list. We then use this to initiate a Python 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. We did this 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.

Call the Sorting Function

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 the sortList function:

numbers = [73, 62, 61, 69]
sortList(numbers)
print("Sorted list:", numbers)

When we run our program, the following is returned:

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

[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 maximum value.

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.

What is the Complexity for the Selection Sort?

The selection sort has a time complexity of O(n2). This means that the complexity of the algorithm will grow exponentially depending on how many elements are in the list.

O(n2) is the worst-case, average, and best-case complexity for this algorithm. If you’d like to learn more about sorting complexities, check out our guide to Big O Notation.

Conclusion

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.

Are you interested in learning more about Python? Read our complete How to Learn Python guide for expert advice to help you advance your knowledge.