Выбор сортировки в Python

1 min


Вступление

Сортировка, хотя и является основной операцией, является одной из наиболее важных операций, которые должен выполнять компьютер. Это строительный блок во многих других алгоритмах и процедурах, таких как поиск и слияние. Знание различных алгоритмов сортировки может помочь вам лучше понять идеи, лежащие в основе разных алгоритмов, а также помочь вам придумать лучшие алгоритмы.

Выбор сортировки Алгоритм сортирует массив, находя минимальное значение несортированной части и затем заменяя его первым несортированным элементом. Это алгоритм на месте, то есть вам не нужно выделять дополнительные списки. Несмотря на медленную скорость, он все еще используется в качестве основного алгоритма сортировки в системах, где память ограничена.

В этой статье мы объясним, как работает сортировка выбора, и реализуем ее в 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],

Начнем с несортированного списка:

В несортированном разделе есть все элементы. Мы просматриваем каждый пункт и определяем, что 1 это самый маленький элемент. Итак, мы поменяемся 1 с 3:

Из оставшихся несортированных элементов [5, 3, 2, 4], 2 это самый низкий номер. Теперь мы поменяемся 2 с 5:

Этот процесс продолжается, пока список не отсортирован:

  • 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 представляющие значения оцененных констант.

Это известно как На2), Что это обозначает? Таким образом, производительность нашего алгоритма основана на квадрате нашего входного списка. Поэтому, если мы удвоим размер нашего списка, время, необходимое для его сортировки, будет умножено на 4! Если мы разделим размер нашего ввода на 3, время сократится на 9!

Вывод

В этой статье мы рассмотрели, как работает Selection Sort, и реализовали его в Python. Затем мы построчно разбили код, чтобы проанализировать временную сложность алгоритма.

Изучение алгоритмов сортировки поможет вам лучше понять алгоритмы в целом. Так что, если вы еще этого не сделали, вы можете проверить наш обзор алгоритмов сортировки!


0 Comments

Ваш адрес email не будет опубликован. Обязательные поля помечены *