Introduction.
The Selection Sort.
In this article, we will explain how the Selection Sort works and implement it in Python. We will then break down the actions of the algorithm to learn its time complexity.
Selection Sort.
A high level implementation of this sort would look something like this:
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]
In the above pseudocode,
argmin() is a function that returns the index of the minimum value. The algorithm uses a variable
i.
The first line increments the value of
i, the second line finds the minimum value's index, and the third line swaps those values. Swapping works because Python calculated the right-hand side before assigning anything to the left-hand side, so we don't need any temporary variables.
Let's see how it works in action with a list that contains the following elements:
[3, 5, 1, 2, 4].
We begin with the unsorted list:
- 3 5 1 2 4
The unsorted section has all the elements. We look through each item and determine that
1 is the smallest element. So, we swap
1 with
3:
- 1 5 3 2 4
Of the remaining unsorted elements,
[5, 3, 2, 4],
2 is the lowest number. We now swap
2 with
5:
- 1 2 3 5 4
This process continues until the list is sorted:
- 1 2 3 5 4
- 1 2 3 4 5
- 1 2 3 4 5
Let's see how we can implement this in Python!
Implementation
The trick to implementing this algorithm is keeping track of the minimum value and swapping two elements of the list. Open a file named
sort.py in your favorite editor and enter the following code in it:]
Now let's add some code to the file to test the algorithm:
L = [3, 1, 41, 59, 26, 53, 59] print(L) selection_sort(L) # Let's see the list after we run the Selection Sort print(L)
You can then open a terminal and run to see the results:
$ python sort.py [3, 1, 41, 59, 26, 53, 59] [1, 3, 26, 41, 53, 59, 59]
The list was correctly sorted! We know how it works and we can implement the Selection Sort in Python. Let's get into some theory and look at its performance with regards to time.
Time Complexity Calculation
So how long does it take for selection sort to sort our list? We are going to take an approach and calculate exactly how much time the selection sort algorithm takes, given an array of size
n. The first line of the code is:
def selection_sort(L):
This line shouldn't take that much since it's only setting the function stack. We say that this is a constant - the size of our input does not change how long it takes for this code to run. Let's say it takes
c1 operations to perform this line of code. Next, we have:
for i in range(len(L)-1):
This one is a little trickier. First of all, we have two function invocations,
len() and
range(), which are performed before the
for loop begins. The cost of
len() is also independent of size in CPython, which is the default Python implementation on Windows, Linux, and Mac. This is also true for the initialization of
range(). Let's call these two together
c2.
Next, we have the
for, which is running
n - 1 times. This is not a constant, the size of the input does make an impact on how long this is executed. So we have to multiply whatever time it takes for one loop to complete by
n - 1.
There is a constant cost for evaluating the
in operator, let's say
c3. That covers the outer for-loop.
The variable assignment is also done in constant time. We'll call this one
c4:
min_index = i
We now encounter the inner for-loop. It has two constant function invocations. Let's say they take
c5 operations.
Note that
c5is different from
c2, because
rangehere has two arguments, and there is an addition operation being performed here.
So far we have
c1 + c2 + (n - 1) * (c3 + c4 + c5) operations, and then our inner loop begins, multiplying everything by...? Well, it's tricky, but if you look closely, it takes
n - 2 times in the first loop,
n - 3 in the second one, and 1 in the last time.
We need to multiply everything by the sum of all numbers between 1 and
n - 2. Mathematicians have told us that the sum would be
(n - 2) * (n - 1) / 2. Feel free to read more about the sum of integers between 1 and any positive number
x here.
The contents of the inner loop are completed in constant time as well. Let's assign the time it takes Python to do the
in,
if, assignment statement and the variable swap take up an arbitrary constant time of
c6.
for j in range(i+1, len(L)-1): if L[j] < L[min_index]: min_index = j L[i], L[min_index] = L[min_index], L[i]
All-together we get
c1 + c2 + (n - 1) * (c3 + c4 + c5) + (n - 2) * (n - 3) * c6 / 2.
We can simplify this to:
a * n * n + b * n + c, where
a,
b and
c representing the values of the evaluated constants.
This is known as O(n2).!
Conclusion
In this article, we looked at how Selection Sort works and implemented it in Python. We then broke the code down line by line to analyze the algorithm's time complexity.
Learning sorting algorithms will help you get a better understanding of algorithms in general. So, in case you haven't already, you can check out our sorting algorithms overview!