Автор оригинала: Sajjad Heydari.
Вступление
Сортировка, хотя и является основной операцией, является одной из самых важных операций, которые должен выполнять компьютер. Это строительный блок во многих других алгоритмах и процедурах, таких как поиск и слияние. Знание различных алгоритмов сортировки может помочь вам лучше понять идеи, лежащие в основе различных алгоритмов, а также помочь вам придумать лучшие алгоритмы.
Алгоритм Selection Sort сортирует массив, находя минимальное значение несортированной части и затем заменяя его первым несортированным элементом. Это алгоритм на месте, то есть вам не нужно будет выделять дополнительные списки. Хотя он медленный, он все еще используется в качестве основного алгоритма сортировки в системах с ограниченной памятью.
В этой статье мы объясним, как работает сортировка выбора и реализуем ее в Python. Затем мы разберем действия алгоритма, чтобы узнать его временную сложность .
Сортировка выбора
Так как же работает сортировка выбора? Сортировка выбора разбивает входной список на две части: отсортированную часть, которая изначально пуста, и несортированную часть, которая изначально содержит список всех элементов. Затем алгоритм выбирает минимальное значение всего несортированного файла и меняет его местами с первым несортированным значением, а затем увеличивает отсортированную часть на единицу.
Высокоуровневая реализация такого рода выглядела бы примерно так:
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]
В приведенном выше псевдокоде argmin () – это функция, возвращающая индекс минимального значения. Алгоритм использует переменную i , чтобы отслеживать, где заканчивается сортированный список и где начинается несортированный. Поскольку мы начинаем без отсортированных элементов и берем минимальное значение, всегда будет иметь место, что каждый член несортированной части больше, чем любой член отсортированной части.
Первая строка увеличивает значение i , вторая строка находит индекс минимального значения, а третья строка меняет эти значения местами. Подкачка работает, потому что Python вычисляет правую сторону, прежде чем назначать что-либо левой стороне, поэтому нам не нужны никакие временные переменные.
Давайте посмотрим, как это работает в действии со списком, содержащим следующие элементы: [3, 5, 1, 2, 4] .
Начнем с несортированного списка:
- 3 5 1 2 4
В несортированном разделе есть все элементы. Мы просматриваем каждый пункт и определяем, что 1 это самый маленький элемент. Итак, мы меняемся местами 1 с 3 :
- 1 5 3 2 4
Из оставшихся несортированных элементов, [5, 3, 2, 4] , 2 это самое низкое число. Теперь мы поменяемся местами 2 с 5 :
- 1 2 3 5 4
Этот процесс продолжается до тех пор, пока список не будет отсортирован:
- 1 2 3 5 4
- 1 2 3 4 5
- 1 2 3 4 5
Давайте посмотрим, как мы можем реализовать это в Python!
Реализация
Хитрость реализации этого алгоритма заключается в отслеживании минимального значения и замене двух элементов списка. Откройте файл с именем sort.py в вашем любимом редакторе и введите в него следующий код:
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]
Теперь давайте добавим немного кода в файл для проверки алгоритма:
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)
Затем вы можете открыть терминал и запустить его, чтобы увидеть результаты:
$ python sort.py [3, 1, 41, 59, 26, 53, 59] [1, 3, 26, 41, 53, 59, 59]
Список был правильно отсортирован! Мы знаем, как это работает, и можем реализовать сортировку выбора в Python. Давайте углубимся в теорию и посмотрим на ее эффективность с точки зрения времени.
Расчет Временной Сложности
Итак, сколько времени требуется для сортировки выбора, чтобы отсортировать наш список? Мы собираемся взять подход и точно рассчитать, сколько времени занимает алгоритм сортировки выбора, учитывая массив размера n . Первая строка кода такова:
def selection_sort(L):
Эта строка не должна занимать так много времени, так как она только устанавливает стек функций. Мы говорим, что это константа – размер наших входных данных не меняется, сколько времени требуется для запуска этого кода. Допустим, для выполнения этой строки кода требуются операции c1 . Далее, у нас есть:
for i in range(len(L)-1):
Этот немного сложнее. Прежде всего, у нас есть два вызова функций, len() и range() , которые выполняются до начала цикла for . Стоимость len() также не зависит от размера в CPython, который является реализацией Python по умолчанию в Windows, Linux и Mac. Это также верно для инициализации range() . Давайте назовем эти два вместе c2 .
Далее у нас есть for , который работает n - 1 раз. Это не константа, размер входных данных действительно влияет на то, как долго это выполняется. Поэтому мы должны умножить любое время, необходимое для завершения одного цикла, на n - 1 .
Существует постоянная стоимость для оценки оператора in , скажем c3 . Это покрывает внешнюю петлю for.
Присвоение переменной также выполняется в постоянном времени. Мы назовем это c4 :
min_index = i
Теперь мы сталкиваемся с внутренней петлей for. Он имеет два постоянных вызова функций. Допустим, они берут c5 операции.
Обратите внимание, что c5 отличается от c2 , потому что range здесь имеет два аргумента, и здесь выполняется операция сложения.
До сих пор у нас есть c1 + c2 + (n - 1) * (c3 + c4 + c5) операции, а затем начинается наш внутренний цикл, умножающий все на…? Ну, это сложно, но если вы посмотрите внимательно, то это займет n - 2 раза в первом цикле, n - 3 во втором и 1 в последний раз.
Нам нужно умножить все на сумму всех чисел от 1 до n - 2 . Математики сказали нам, что сумма будет (n - 2) * (n - 1)/2 . Не стесняйтесь читать больше о сумме целых чисел от 1 до любого положительного числа x | здесь .
Содержимое внутреннего цикла также завершается в постоянном времени. Давайте назначим время, необходимое Python для выполнения оператора присваивания in , if , а переменная swap займет произвольное постоянное время 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]
Все вместе мы получаем c1 + c2 + (n - 1) * (c3 + c4 + c5) + (n - 2) * (n - 3) * c6/2 .
Мы можем упростить это до: a * n * n + b * n + c , где a , b и c представляют значения вычисляемых констант.
Это известно как O(n 2 ) . Что это значит? Таким образом, производительность нашего алгоритма основана на квадрате размера нашего входного списка. Поэтому, если мы удвоим размер нашего списка, время, необходимое для его сортировки, будет умножено на 4! Если мы разделим размер наших входных данных на 3, время сократится на 9!
Вывод
В этой статье мы рассмотрели, как работает сортировка выбора и реализовали ее в Python. Затем мы разбили код по строкам, чтобы проанализировать временную сложность алгоритма.
Изучение алгоритмов сортировки поможет вам лучше понять алгоритмы в целом. Так что, если вы еще этого не сделали, вы можете ознакомиться с нашим обзором алгоритмов сортировки !