Selection Sort in Python
Sorting, although a basic operation, is one of the most important operations a computer should perform. It is a building block in many other algorithms and procedures, such as searching and merging. Knowing different sorting algorithms could help you better understand the ideas behind the different algorithms, as well as help you come up with better algorithms.
The Selection Sort algorithm sorts an array by finding the minimum value of the unsorted part and then swapping it with the first unsorted element. It is an in-place algorithm, meaning you won’t need to allocate additional lists. While slow, it is still used as the main sorting algorithm in systems where memory is limited.
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
So how does the selection sort work? Selection sort breaks the input list in two parts, the sorted part which initially is empty, and the unsorted part, which initially contains the list of all elements. The algorithm then selects the minimum value of all the unsorted file and swaps it with the first unsorted value, and then increases the sorted part by one.
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 to keep track of where the sorted list ends and where the unsorted one begins. Since we start with no sorted items and take the minimum value, it will always be the case that every member of the unsorted part is greater than any member of the sorted part.
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:
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 :
Of the remaining unsorted elements, [5, 3, 2, 4] , 2 is the lowest number. We now swap 2 with 5 :
This process continues until the list is sorted:
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:
def selection_sort(L): # i indicates how many items were sorted for i in range(len(L)-1): # To find the minimum value of the unsorted segment # We first assume that the first element is the lowest min_index = i # We then use j to loop through the remaining elements for j in range(i+1, len(L)-1): # Update the min_index if the element at j is lower than it if L[j] < L[min_index]: min_index = j # After finding the lowest item of the unsorted regions, swap with the first unsorted item L[i], L[min_index] = L[min_index], L[i] 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:
Free eBook: Git Essentials
Check out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually learn it!
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:
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 :
We now encounter the inner for-loop. It has two constant function invocations. Let’s say they take c5 operations.
Note that c5 is different from c2 , because range here 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(n 2 ). What does that mean? In summary, our algorithm's performance is based on the squared size of our input list. Therefore, if we double the size of our list, the time it takes to sort it would be multiplied by 4! If we divide the size of our input by 3, the time would shrink by 9!
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!
Сортировка выбором
Алгоритм сортировки выбором заключается в поиске на необработанном срезе массива или списка минимального значения и в дальнейшем обмене этого значения с первым элементом необработанного среза (поиск минимума и перестановка). На следующем шаге необработанный срез уменьшается на один элемент.
- Найти наименьшее значение в списке.
- Записать его в начало списка, а первый элемент - на место, где раньше стоял наименьший.
- Снова найти наименьший элемент в списке. При этом в поиске не участвует первый элемент.
- Второй минимум поместить на второе место списка. Второй элемент при этом перемещается на освободившееся место.
- Продолжать выполнять поиcк и обмен, пока не будет достигнут конец списка.
Решение задачи на языке программирования Python:
# Заполняем список из 10 элементов # случайными числами от 1 до 99 и # выводим неотсортированный список на экран. from random import randint N = 10 arr = [] for i in range(N): arr.append(randint(1, 99)) print(arr) # В цикле переменная i хранит индекс ячейки, # в которую записывается минимальный элемент. # Сначала это будет первая ячейка. i = 0 # N - 1, так как последний элемент # обменивать уже не надо. while i N - 1: # ПОИСК МИНИМУМА # Сначала надо найти минимальное значение # на срезе от i до конца списка. # Переменная m будет хранить индекс ячейки # с минимальным значением. # Сначала предполагаем, что # в ячейке i содержится минимальный элемент. m = i # Поиск начинаем с ячейки следующей за i. j = i + 1 # Пока не дойдем до конца списка, while j N: # будем сравнивать значение ячейки j, # со значением ячейки m. if arr[j] arr[m]: # Если в j значение меньше, чем в m, # сохраним в m номер найденного # на данный момент минимума. m = j # Перейдем к следующей ячейке. j += 1 # ОБМЕН ЗНАЧЕНИЙ # В ячейку i записывается найденный минимум, # а значение из ячейки i переносится # на старое место минимума. arr[i], arr[m] = arr[m], arr[i] # ПЕРЕХОД К СЛЕДУЮЩЕЙ НЕОБРАБОТАННОЙ ЯЧЕЙКЕ i += 1 # Вывод отсортированного списка print(arr)
[77, 46, 11, 89, 48, 14, 67, 73, 22, 26] [11, 14, 22, 26, 46, 48, 67, 73, 77, 89]
Сортировка выбором с помощью цикла for и помещения реализации алгоритма в функцию:
from random import randint N = 10 def sel_sort(row): n = len(row) for i in range(n-1): m = i for j in range(i+1, n): if row[j] row[m]: m = j row[i], row[m] = row[m], row[i] arr = [randint(1, 99) for item in range(N)] print(arr) sel_sort(arr) print(arr)