Алгоритмы сортировки на Python

Сортировка — это базовый элемент построения многих алгоритмов и связана она с захватывающими идеями. Понимание того, как за кулисами в Python работают алгоритмы сортировки, является основополагающим шагом при реализации правильных и эффективных алгоритмов, решающих реальные проблемы.

В этом уроке вы узнаете:

• Как работают различные алгоритмы сортировки в Python и как их сравнивать в разных обстоятельствах.
• Как за кулисами работает встроенная функция сортировки Python.
• Как такие понятия компьютерных наук, как рекурсии и разделяй и властвуй применимы к сортировке.
• Как измерять эффективность алгоритмов, используя нотацию «О»‑большое и модуль timeit Python

В результате вы поймете как с теоретической, так и с практической точек зрения, что такое алгоритмы сортировки. Сможете использовать различные методы при разработке алгоритмов, которые можно использовать и в других областях своей работы. Давайте начинать!

Содержание

Почему алгоритмов сортировки так важны?

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

• Поиск: Поиск элемента в списке работает намного быстрее, если список отсортирован.
• Выбор: с помощью отсортированных данных легче выбирать элементы из списка на основе их места по отношению к другим элементам. Например, найти k-^е самое большое или наименьшее значение или найти медианное значение списка намного проще, если значения находятся в порядке возрастания или убывания.
• Поиск дубликатов: поиск одинаковых значений в списке можно выполнить очень быстро, если список отсортирован.
• Распределение: Анализ распределения элементов в списке выполняется очень быстро, если список отсортирован. Например, найти элемент, который появляется наиболее или наименее часто, относительно просто в отсортированном списке.

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

Встроенный алгоритм сортировки

Python, как и многие другие языки программирования высокого уровня, имеют функции сортировки прямо из коробки, например, sorted() в Python:

>>> array = [8, 2, 6, 4, 5]
>>> sorted(array)
[2, 4, 5, 6, 8]

Для сортировки любого списка можно использовать функцию sorted() при условии, что значения внутри списка можно сравнивать.

Примечание.

Для более глубокого погружения в работу встроенной функции сортировки Python, ознакомьтесь с разделом Как использовать sorted() и sort() в Python и Сортировка данных с помощью Python.

Почему так важно знать вычислительную сложность?

Вычислительная сложность^એ — фундаментальное понятие вычислительной математики. В этом уроке рассматриваются два разных способа измерения сложности алгоритмов сортировки:

1. Практический, когда для измерения сложности будет использован модуль timeit.
2. Более теоретический, когда измеряется вычислительная сложность алгоритмов с использованием нотации «O» большое и «o» малое^એ.

Вычислительная сложность вашего кода

При сравнении двух алгоритмов сортировки в Python всегда полезно посмотреть, сколько времени занимает каждый из них. Конкретное время, которое занимает каждый алгоритм, будет частично определяться вашим оборудованием, но вы все равно можете использовать пропорциональное время между выполнениями, чтобы помочь вам решить, какая реализация более эффективна по времени. В этом разделе вы сосредоточитесь на практическом (экспериментальном) способе определения фактического времени, необходимого для выполнения ваших алгоритмов сортировки с использованием модуля timeit. Для получения дополнительной информации о различных способах измерения времени выполнения кода в Python, ознакомьтесь с функциями времени Python: три способа контроля своего кода. Вот функция, которая поможет нам оценить время выполнения алгоритмов:

from random import randint
from timeit import repeat

def run_sorting_algorithm(algorithm, array):
    # Настройте контекст и подготовьте вызов указанного Алгоритма
    # с использованием предоставленного массива. Только импортировать
    # функция алгоритма, если это не встроенная функция sorted()
    setup_code = f"from __main__ import {algorithm}" \
	if algorithm != "sorted" else ""

    stmt = f"{algorithm}({array})"

    # Выполнить код десять раз и каждый раз
    # вернуть время в секундах
    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)

    # Наконец, покажите название алгоритма и
    # минимальное время, необходимое для его выпонения
    print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")

В этом примере run_sorting_algorithm() получает имя алгоритма и входной массив, который необходимо отсортировать. Вот построчное объяснение того, как это работает:

• Строка 8 импортирует имя алгоритма, используя магию f-строк Python. Таким образом, timeit.repeat() узнает, откуда вызывать алгоритм. Обратите внимание, что это необходимо только для пользовательских реализаций, используемых в этом уроке. Если указанный алгоритм является встроенным, наприер, sorted(), то ничего не будет импортировано.
• Строка 11 готовит вызов алгоритма с предоставленным массивом. Это описание для выполнения и оценки времени.
• Строка 15 вызывает timeit.repeat() с кодом настройки и оператором. Это вызовет указанный алгоритм сортировки десять раз, возвращая количество секунд, которое потребовалось каждому из этих исполнений.
• Строка 19 находит самое короткое время выполнения и печатает его вместе с именем алгоритма.

Примечание:

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

Вот пример того, как использовать, run_sorting_algorithm() для оценки времени, необходимого для сортировки массива из десяти тысяч целочисленных значений, используя sorted() :

ARRAY_LENGTH = 10000

if __name__ == "__main__":
   # Сгенерировать массив элементов `ARRAY_LENGTH`, состоящий из
   # случайных целых значений от 0 до 999
   array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]
 
   # Вызвать функцию, используя имя алгоритма сортировки
   # и массив, который вы только что создали, передать ей
   run_sorting_algorithm(algorithm="sorted", array=array)

Если вы сохраните приведенный выше код в файле sorting.py, то сможете запустить его из терминала и посмотреть на результат:

$ python sorting.py
Algorithm: sorted. Minimum execution time: 0.010945824000000007

Помните, что время в секундах каждого эксперимента частично зависит от используемого вами оборудования, поэтому вы, скорее всего, увидите несколько иные результаты при запуске кода.

Примечание:

Узнать больше о модуле timeit можно в официальной документации Python.

Вычислительная сложность^એ в нотации «О»‑большое

Конкретного времени, которое требуется алгоритму недостаточно для получения полной картины его вычислительной сложности. Чтобы решить эту проблему, вы можете использовать обозначение «О»‑большое. «О»‑большое часто используется для сравнения различных реализаций и определения, какая из них наиболее эффективна, пропуская ненужные детали и концентрируясь на том, что является наиболее важным во время выполнения алгоритма. Время в секундах, необходимое для запуска различных алгоритмов, может зависеть от нескольких несвязанных факторов, включая скорость процессора или доступную память. «О»‑большое, с другой стороны, предоставляет платформу для выражения вычислительной сложности выполнения в не зависящем от аппаратного обеспечения виде. «О»‑большое показывает, как быстро увеличивается время выполнения вашего алгоритма в зависимости от размера входных данных, особенно когда входные данные становятся очень большими. Предполагая, что n — это размер входных данных алгоритма, нотация «О»‑большое представляет взаимосвязь между n и числом шагов, которые выполняет алгоритм до своего завершения. «О»‑большое использует заглавную букву «О», за которой в скобках следует обозначение зависимости. Например, O(n) представляет алгоритмы, которые выполняют последовательность шагов, количество которых пропорционально размеру входных данных. Хотя в этом уроке мы не собираемся углубляться в детали нотации «О»‑большое, но вот вам пять примеров вычислительной сложности различных алгоритмов:

В этом уроке для каждого из обсуждаемых алгоритмов сортировки рассматривается вычислительная сложность «O» большое и «o» малое^એ. Кроме того, есть краткое объяснение того, как определить сложность в каждом конкретном случае. Это поможет вам лучше понять, как начать использовать «О»‑большое для классификации других алгоритмов.

Алгоритм сортировки методом «пузырька»

Метод «пузырька» или обменная сортировка — один из самых простых алгоритмов сортировки. Его название происходит от того, как работает алгоритм: с каждым новым проходом самый большой элемент «всплывает» к своему месту в упорядоченном списке. Пузырьковая сортировка состоит из нескольких проходов по списку, поэлементному сравнению с соседним элементом и, при необходимости, сменой порядка следования этих элементов.

Сортировка в Python методом «пузырька»

Вот реализация алгоритма сортировки «пузырьком» или обменная сортировка в Python:

def bubble_sort(array):
    n = len(array)

    for i in range(n):
        # Начните просматривать каждый элемент списка один за другим,
        # сравнивая его с соседним значением. С каждым
        # итерация, часть массива, на которую вы смотрите
        # сжимается, потому что остальные элементы уже были
        # отсортировано.
        for j in range(n - i - 1):
            # Создать флаг, который позволит функции
            # преждевременно завершить работу, если нечего сортировать
            already_sorted = True

            if array[j] > array[j + 1]:
                # Если объект, на который вы смотрите, больше, чем его
                # соседнее значение, затем поменяйте их местами
                array[j], array[j + 1] = array[j + 1], array[j]

                # Поскольку вам пришлось поменять местами два элемента,
                # устанавливаем флаг ʻalready_sorted` на `False`, чтобы
                # алгоритм не завершается преждевременно
                already_sorted = False

        # Если на последней итерации не было свопов,
        # массив уже отсортирован, и вы можете завершить
        if already_sorted:
            break

    return array

Поскольку эта реализация упорядочивает массив по возрастанию, то на каждом шаге самый большой элемент «откладывается» в конце массива. Это означает, что каждая последующая итерация занимает меньше шагов, чем предыдущая. Циклы в строке 10 определяют способ просмотра списка. Обратите внимание, как j изначально идет от первого элемента в списке к элементу непосредственно перед последним. Во время второй итерации j цикл выполняется до второго элемента от последнего, затем до третьего элемента от последнего и т.д. В конце каждой итерации конечная часть списка будет отсортирована. По мере прохождения цикла строка 15 сравнивает каждый элемент с соседним значением, а строка 18 меняет их местами, если они находятся в неправильном порядке. Это гарантирует получение отсортированного списка при завершении алгоритма.

Примечание:

Флаг already_sorted в строках 13, и приведенного выше кода оптимизирует алгоритм и не требуется в полнофункциональной реализации пузырьковой сортировки. Тем не менее, он позволяет функции сохранять ненужные шаги, если список полностью сортируется до завершения циклов. В качестве упражнения вы можете отказаться от использования этого флага и сравнить время выполнения обеих реализаций.

Чтобы правильно проанализировать, как работает алгоритм, рассмотрим список со значениями [8, 2, 6, 4, 5]. Предположим, вы используете bubble_sort() сверху. Вот рисунок, иллюстрирующий, как выглядит массив на каждой итерации алгоритма:

Теперь пошагово посмотрим, что происходит с массивом в процессе работы алгоритма:

1. Код начинается со сравнения первого элемента 8 со смежным элементом 2. Так 8 > 2, значения меняются местами, в результате чего в следующем порядке: [2, 8, 6, 4, 5].
2. Затем алгоритм сравнивает второй элемент 8 со смежным элементом 6. Так 8 > 6, значения меняются местами, в результате чего в следующем порядке: [2, 6, 8, 4, 5].
3. Затем алгоритм сравнивает третий элемент 8 со смежным элементом 4. Так 8 > 4, он меняет местами значения, а также, в результате чего в следующем порядке: [2, 6, 4, 8, 5].
4. Наконец, алгоритм сравнивает четвертый элемент 8 со смежным элементом 5 и заменяет их, что приводит к [2, 6, 4, 5, 8]. На этом этапе алгоритм завершил первый проход по списку ( i = 0 ). Обратите внимание, как значение 8 всплыло из исходного положения в правильное положение в конце списка.
5. Второй проход ( i = 1 ) учитывает, что последний элемент списка уже расположен, и фокусируется на оставшихся четырех элементах [2, 6, 4, 5]. В конце этого прохода значение 6 находит свою правильную позицию. Третий проход по списку позиционирует значение 5 и так далее, пока список не будет отсортирован.

Оценка вычислительной сложности метода «пузырька»

Реализация сортировки методом «пузырька» состоит из двух вложенных циклов for, в которых алгоритм выполняет n - 1 сравнение, затем n - 2 сравнения и так далее, пока не будет выполнено последнее сравнение в списке. В итоге получается (n - 1) + (n - 2) + (n - 3) + … + = n \times \frac{(n-1)}{2} сравнения, которые также можно записать как \frac{1}{2}n^2 - \frac{1}{2}n, Ранее вы узнали, что «О»‑большое фокусируется на том, как увеличивается время выполнения в зависимости от размера входных данных. Это означает, что для того, чтобы превратить вышеприведенное уравнение в сложность алгоритма «О»‑большое, вам нужно удалить константы, потому что они не меняются в зависимости от размера ввода. Это упрощает запись до n^2 - n. Поскольку n^2 растет намного быстрее, чем n, этот последний член также можно отбросить, оставляя пузырьковую сортировку со средней и наихудшей сложностью O(n^2). В тех случаях, когда алгоритм получает массив, который уже отсортирован — и при условии, что реализация включает в себя already_sorted оптимизацию флага, описанную ранее, — сложность времени выполнения снизится до гораздо лучшего значения O(n), поскольку алгоритму не нужно будет сравнивать любой элемент более одного раза,

Таким образом, а O(n) — сложность выполнения алгоритма методом «пузырька». Но надо иметь в виду, что лучший случай скорее исключением, а нам при сравнении различных алгоритмов надо сосредоточиться на более вероятных случаях.

Оценка времени выполнения алгоритма метода «пузырька»

Используем для вычисления времени выполнения алгоритма сортировки методом «пузырька» уже известный нам run_sorting_algorithm() для обработки массива с десятью тысячами элементов. В строке 8 заменим имя алгоритма, а все остальное оставим прежним:

if __name__ == "__main__":
    # Generate an array of `ARRAY_LENGTH` items consisting
    # of random integer values between 0 and 999
    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]

    # Call the function using the name of the sorting algorithm
    # and the array you just created
    run_sorting_algorithm(algorithm="bubble_sort", array=array)

Теперь можно запустить скрипт и получить время выполнения bubble_sort :

$ python sorting.py
Algorithm: bubble_sort. Minimum execution time: 73.21720498399998

Потребовалось чуть больше 73 секунд для сортировки массива из десяти тысяч элементов. Это минимальное время из десяти run_sorting_algorithm() запущенных повторений. Многократное выполнение этого скрипта даст схожие результаты.

Примечание:

Однократное выполнение пузырьковой сортировки заняло чуть более 73 секунд, но используя timeit.repeat(), алгоритм выполнялся десять раз. Таким образом, выполнение всего кода займет около 73 * 10 = 730 секунд, при условии, что у нас сходные аппаратные характеристики. На более медленных машинах это может занять гораздо больше времени.

Преимущества и недостатки сортировки методом «пузырька» в Python

Основным преимуществом алгоритма пузырьковой сортировки является его простота. Его легко реализовать и понять. Вероятно, это основная причина, по которой большинство курсов по информатике вводят тему сортировки с использованием пузырьковой сортировки. Как вы видели ранее, недостатком пузырьковой сортировки является то, что она медленная, со сложностью времени выполнения O(n^2). К сожалению, это исключает его из практических претендентов на сортировку больших массивов.

Алгоритм сортировки методом вставки

Подобно пузырьковой сортировке, алгоритм сортировки вставкой прост в реализации и понимании. Но в отличие от пузырьковой сортировки, он создает отсортированный список по одному элементу за раз, сравнивая каждый элемент с остальной частью списка и вставляя его в нужное место. Эта процедура «вставки» дает алгоритму его имя. Отличная аналогия для объяснения сортировки вставками — это способ сортировки колоды карт. Представьте, что вы держите в руках группу карт и хотите расположить их по порядку. Вы начнете со сравнения одной карты шаг за шагом с остальными картами, пока не найдете правильную позицию. В этот момент вы вставите карту в правильное место и начнете сначала с новой карты, повторяя, пока все карты в вашей руке не будут отсортированы.

Сортировка в ​​Python методом вставки

Алгоритм сортировки вставок работает точно так же, как в примере с колодой карт. Вот реализация в Python:

def insertion_sort(array):
    # Цикл от второго элемента массива до
    # последний элемент
    for i in range(1, len(array)):
        # Это элемент, который мы хотим разместить в
        # правильное место
        key_item = array[i]

        # Инициализировать переменную, которая будет использоваться для
        # найти правильную позицию указанного элемента
        # `key_item`
        j = i - 1

        # Просмотрите список элементов (слева
        # часть массива) и найдите правильную позицию
        # элемента, на который ссылается `key_item`. Сделай это только
        # если key_item меньше соседних значений.
        while j >= 0 and array[j] > key_item:
            # Сдвинуть значение на одну позицию влево
            # и переместите j, чтобы указать на следующий элемент
            # (справа налево)
            array[j + 1] = array[j]
            j -= 1

        # Когда вы закончите сдвигать элементы, вы можете расположить
        # `key_item` в правильном месте
        array[j + 1] = key_item

    return array

В отличие от пузырьковой сортировки, эта реализация сортировки вставкой создает отсортированный список, перемещая меньшие элементы влево. Давайте разберем insertion_sort() построчно:

• Строка 4 устанавливает цикл, который определяет, key_item что функция будет позиционировать во время каждой итерации. Обратите внимание, что цикл начинается со второго элемента в списке и продолжается до последнего элемента.
• Строка 7 инициализируется key_item с элементом, который функция пытается разместить.
• Строка 12 инициализирует переменную, которая будет последовательно указывать на каждый элемент слева от key item. Это элементы, которые будут последовательно сравниваться key_item.
• Строка 18 сравнивается key_item с каждым значением слева, используя while цикл, смещая элементы, чтобы освободить место для размещения key_item.
• Строка располагается key_item на своем правильном месте после того, как алгоритм сдвигает все большие значения вправо.

Вот рисунок, иллюстрирующий различные итерации алгоритма при сортировке массива [8, 2, 6, 4, 5] :

Теперь вот краткое изложение шагов алгоритма при сортировке массива:

1. Алгоритм начинается с key_item = 2 и проходит через подмассив слева, чтобы найти правильную позицию для него. В этом случае подмассив есть [8].
2. Поскольку 2 < 8 алгоритм сдвигает элемент на 8 одну позицию вправо. Полученный массив в этой точке [8, 8, 6, 4, 5].
3. Поскольку в подмассиве больше нет элементов, объект key_item теперь находится в новой позиции, а окончательный массив — [2, 8, 6, 4, 5].
4. В этом случае второй проход начинается с key_item = 6 и проходит через подмассив, расположенный слева от него [2, 8].
5. Поскольку 6 < 8 алгоритм сдвигается навправо. Полученный массив в этой точке [2, 8, 8, 4, 5].
6. Поскольку 6 > 2 алгоритму не нужно продолжать проходить через подмассив, он позиционирует key_item и заканчивает второй проход. В это время результирующий массив имеет вид [2, 6, 8, 4, 5].
7. Третий проход по списку помещает элемент 4 в правильное положение, а четвертый проход помещает элемент 5 в правильное место, оставляя массив отсортированным.

Оценка сложности «О»‑большое алгоритма вставки

Подобно вашей реализации пузырьковой сортировки, алгоритм вставной сортировки имеет несколько вложенных циклов, которые идут по списку. Внутренний цикл довольно эффективен, потому что он проходит по списку, пока не найдет правильную позицию элемента. Тем не менее, алгоритм все еще имеет O(n^2) сложность времени выполнения в среднем случае. Худший случай случается, когда предоставленный массив сортируется в обратном порядке. В этом случае внутренний цикл должен выполнять каждое сравнение, чтобы поместить каждый элемент в правильное положение. Это все еще дает вам O(n^2) сложность во время выполнения. Наилучший случай случается, когда предоставленный массив уже отсортирован. Здесь внутренний цикл никогда не выполняется, что приводит к сложности выполнения O(n), как в лучшем случае пузырьковой сортировки. Хотя пузырьковая сортировка и вставка сортировки имеют одинаковую сложность во время выполнения «О»‑большое, на практике вставка сортировки значительно эффективнее, чем пузырьковая сортировка. Если вы посмотрите на реализацию обоих алгоритмов, то увидите, как сортировка вставками должна выполнять меньше сравнений для сортировки списка.

Оценка времени выполнения сортировки вставкой

Чтобы доказать утверждение, что сортировка вставками более эффективна, чем сортировка по пузырькам, вы можете рассчитать время выполнения алгоритма сортировки по вставке и сравнить его с результатами сортировки по пузырькам. Для этого вам просто нужно заменить вызов run_sorting_algorithm() на имя вашей реализации сортировки вставкой:

if __name__ == "__main__":
    # Сгенерировать массив элементов ARRAY_LENGTH, состоящий из
    # случайных целочисленных значений от 0 до 999
    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]

    # Вызываем функцию по имени алгоритма сортировки
    # и только что созданный массив
    run_sorting_algorithm(algorithm="insertion_sort", array=array)

Вы можете выполнить скрипт как раньше:

$ python sorting.py
Algorithm: insertion_sort. Minimum execution time: 56.71029764299999

Обратите внимание, что реализация сортировки вставкой заняла примерно 17 меньше секунд, чем реализация пузырьковой сортировки, чтобы отсортировать тот же массив. Даже при том, что они оба O(n^2) алгоритмы, сортировка вставки более эффективна.

Преимущества и недостатки сортировки вставкой

Алгоритм сортировки вставками, как и пузырьковая сортировка, очень прост в реализации. Несмотря на то, что сортировка вставкой является алгоритмом O(n^2), на практике он также намного эффективнее, чем другие квадратичные реализации, такие как пузырьковая сортировка. Существуют более мощные алгоритмы, включая сортировку слиянием и быструю сортировку, но эти реализации рекурсивны и обычно не справляются с сортировкой вставки при работе с небольшими списками. Некоторые реализации быстрой сортировки даже используют внутреннюю сортировку, если список достаточно мал, чтобы обеспечить более быструю общую реализацию. Timsort также использует внутреннюю сортировку для сортировки небольших частей входного массива. Тем не менее, сортировка с вставкой непрактична для больших массивов, открывая двери для алгоритмов, которые могут масштабироваться более эффективными способами.

Алгоритм сортировки слиянием

Сортировка слиянием — очень эффективный алгоритм сортировки. Он основан на подходе «разделяй и властвуй», мощном алгоритмическом методе, используемом для решения сложных задач. Чтобы правильно понять «разделяй и властвуй», вы должны сначала понять концепцию рекурсии. Рекурсия включает разбиение проблемы на более мелкие подзадачи, пока они не станут достаточно маленькими для управления. В программировании рекурсия обычно выражается функцией, вызывающей себя.
Примечание:

В этом урок мы не углубляемся в рассматрение рекурсии. Чтобы лучше понять, как работает рекурсия и увидеть ее в действии с использованием Python, ознакомьтесь с разделом «Рекурсивное мышление» в Python.

Алгоритмы «разделяй и властвуй» обычно имеют одинаковую структуру:

1. Исходные данные разбиваются на несколько частей, каждая из которых представляет собой подзадачу, аналогичную исходной, но более простую.
2. Каждая подзадача решается рекурсивно.
3. Решения всех подзадач объединяются в единое общее решение.

В случае сортировки слиянием подход «разделяй и властвуй» делит набор входных значений на две части одинакового размера, рекурсивно сортирует каждую половину и, наконец, объединяет эти две отсортированные части в один отсортированный список.

Сортировка в Python методом слиянием

Реализация алгоритма сортировки слиянием требует двух разных частей:

1. Функция, которая рекурсивно разбивает входные данные пополам.
2. Функция, которая объединяет обе половины, создавая отсортированный массив.

Вот код для объединения двух разных массивов:

def merge(left, right):
    # Если первый массив пуст, то ничего не нужно
    # для объединения, и вы можете вернуть второй массив в качестве результата
    if len(left) == 0:
        return right

    # Если второй массив пуст, то ничего не нужно
    # для объединения, и вы можете вернуть первый массив как результат
    if len(right) == 0:
        return left

    result = []
    index_left = index_right = 0

    # Теперь перебираем оба массива, пока все элементы
    # превратить его в результирующий массив
    while len(result) < len(left) + len(right):
        # Элементы необходимо отсортировать, чтобы добавить их в
        # результирующий массив, поэтому вам нужно решить, получать ли
        # следующий элемент из первого или второго массива
        if left[index_left] <= right[index_right]:
            result.append(left[index_left])
            index_left += 1
        else:
            result.append(right[index_right])
            index_right += 1

        # Если вы дойдете до конца любого массива, вы можете
        # добавляем оставшиеся элементы из другого массива в
        # результат и разорвать цикл
        if index_right == len(right):
            result += left[index_left:]
            break

        if index_left == len(left):
            result += right[index_right:]
            break

    return result

merge() получает два разных отсортированных массива, которые необходимо объединить. Процесс для достижения этого прост:

• Строкии 9 проверяют, пуст ли один из массивов. Если один из них есть, тогда объединять нечего, поэтому функция возвращает другой массив.
• Строка 17 запускает while цикл, который заканчивается всякий раз, когда результат содержит все элементы из обоих предоставленных массивов. Цель состоит в том, чтобы просмотреть оба массива и объединить их элементы, чтобы получить отсортированный список.
• Строка 21 сравнивает элементы в начале обоих массивов, выбирает меньшее значение и добавляет его в конец результирующего массива.
• Строки 31 и 35 добавляют все оставшиеся элементы к результату, если все элементы из любого из массивов уже были использованы.

При наличии вышеуказанной функции единственным отсутствующим элементом является функция, которая рекурсивно разделяет входной массив пополам и использует merge() для получения окончательного результата:

def merge_sort(array):
    # Если входной массив содержит менее двух элементов,
    # затем вернуть его как результат функции
    if len(array) < 2:
        return array

    midpoint = len(array) // 2

    # Сортировать массив, рекурсивно разделяя ввод
    # на две равные половины, каждую половину сортируя и объединяя
    # вместе в окончательный результат
    return merge(
        left=merge_sort(array[:midpoint]),
        right=merge_sort(array[midpoint:]))

Вот краткое описание кода:

• Строка 44 действует как условие остановки рекурсии. Если входной массив содержит менее двух элементов, то функция возвращает массив. Обратите внимание, что это условие может быть вызвано получением одного элемента или пустого массива. В обоих случаях сортировать нечего, поэтому функция должна вернуться.
• Строка 47 вычисляет среднюю точку массива.
• Линия 52 вызывает merge(), передавая обе отсортированные половины как массивы.

Обратите внимание, как эта функция вызывает себя рекурсивно, каждый раз уменьшая массив пополам. Каждая итерация имеет дело с постоянно уменьшающимся массивом до тех пор, пока не останется менее двух элементов, то есть сортировать нечего. В этот момент merge() вступает во владение, объединяя две половины и создавая отсортированный список. Посмотрите на представление шагов, которые сортировка слиянием предпримет для сортировки массива [8, 2, 6, 4, 5] :

На рисунке используются желтые стрелки для представления деления массива пополам на каждом уровне рекурсии. Зеленые стрелки представляют слияние каждого подмассива обратно вместе. Шаги можно суммировать следующим образом:

1. Первый вызов merge_sort() с [8, 2, 6, 4, 5] определяет midpoint как 2. midpoint Используется для ввода вдвое сократить массив в array[:2] и array[2:], производя [8, 2] и [6, 4, 5], соответственно. merge_sort() затем рекурсивно вызывается для каждой половины сортировать их отдельно.
2. Призыв к merge_sort() с [8, 2] производит [8] и [2]. Процесс повторяется для каждой из этих половин.
3. Вызов merge_sort() with [8] возвращает, [8] так как это единственный элемент. То же самое происходит с призывом к merge_sort() с [2].
4. В этот момент функция начинает объединять подмассивы обратно, используя merge(), начиная с [8] и в [2] качестве входных массивов, создавая [2, 8] результат.
5. С другой стороны, [6, 4, 5] рекурсивно разбивается и объединяется с использованием той же процедуры, что приводит [4, 5, 6] к результату.
6. На конечной стадии, [2, 8] и [4, 5, 6] объединяются вместе с merge(), производя конечный результат: [2, 4, 5, 6, 8].

Оценка сложности "О"‑большое алгоритма сортировки слиянием

Чтобы проанализировать сложность сортировки слиянием, вы можете взглянуть на два ее шага отдельно:

1. merge() имеет линейное время выполнения. Он получает два массива, общая длина которых не более n (длина исходного входного массива), и объединяет оба массива, просматривая каждый элемент не более одного раза. Это приводит к сложности выполнения O(n).
2. Второй шаг рекурсивно разбивает входной массив и вызывает merge() каждую половину. Поскольку массив делится пополам, пока не останется один элемент, общее число операций деления пополам, выполняемых этой функцией, составляет log ₂ n. Поскольку merge() вызывается для каждой половины, мы получаем общее время выполнения O(n \log{n}).

Интересно, что O(n \log{n}) - это наилучшее время выполнения в худшем случае, которое может быть достигнуто алгоритмом сортировки.

Оценка времени выполнения сортировки слиянием

Чтобы сравнить скорость сортировки слиянием с двумя предыдущими реализациями, вы можете использовать тот же механизм, что и раньше, и заменить имя алгоритма в строке 8 :

if __name__ == "__main__":
    # Сгенерировать массив элементов ARRAY_LENGTH, состоящий из
    # случайных целочисленных значений от 0 до 999
    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]

   # Вызываем функцию по имени алгоритма сортировки
    # и только что созданный массив
    run_sorting_algorithm(algorithm="merge_sort", array=array)

Вы можете выполнить скрипт, чтобы получить время выполнения merge_sort :

$ python sorting.py
Algorithm: merge_sort. Minimum execution time: 0.6195857160000173

По сравнению с пузырьковой сортировкой и сортировкой вставкой реализация сортировки слиянием чрезвычайно быстра, сортируя массив из десяти тысяч элементов менее чем за секунду!

Преимущества и недостатки сортировки слиянием

Благодаря вычислительной сложности выполнения O(n \log{n}) сортировка слиянием является очень эффективным алгоритмом, который хорошо масштабируется по мере увеличения размера входного массива. Это также просто для распараллеливания, поскольку он разбивает входной массив на куски, которые могут быть распределены и обрабатываются параллельно, если это необходимо. Тем не менее, для небольших списков затраты времени на рекурсию позволяют таким алгоритмам, как пузырьковая сортировка и вставка сортировки, быть быстрее. Например, выполнение эксперимента со списком из десяти элементов приводит к следующему времени:

Algorithm: bubble_sort. Minimum execution time: 0.000018774999999998654
Algorithm: insertion_sort. Minimum execution time: 0.000029786000000000395
Algorithm: merge_sort. Minimum execution time: 0.00016983000000000276

При сортировке списка из десяти элементов как пузырьковая сортировка, так и сортировка вставкой превосходят сортировку слиянием. Другим недостатком сортировки слиянием является то, что он создает копии массива при рекурсивном вызове себя. Он также создает новый список внутри merge() для сортировки и возврата обеих входных половин. Это заставляет сортировку слиянием использовать гораздо больше памяти, чем пузырьковую сортировку и сортировку вставкой, которые могут сортировать список по месту. Из-за этого ограничения вы можете не использовать сортировку слиянием для сортировки больших списков на оборудовании с ограниченным объемом памяти.

Алгоритм быстрой сортировки в Python

Как и сортировка слиянием, алгоритм быстрой сортировки применяет принцип «разделяй и властвуй» для разделения входного массива на два списка: первый с небольшими элементами, а второй с большими элементами. Затем алгоритм рекурсивно сортирует оба списка, пока результирующий список не будет полностью отсортирован. Разделение входного списка называется разделением списка. Quicksort сначала выбирает pivot элемент и разбивает список вокруг pivot, помещая каждый меньший элемент в low массив и каждый больший элемент в high массив. Помещение каждого элемента из low списка слева от pivot и каждого элемента из high списка вправо помещает pivot именно то место, где оно должно быть в конечном отсортированном списке. Это означает, что теперь функция может рекурсивно применять одну low и ту же процедуру к и high до тех пор, пока весь список не будет отсортирован.

Быстрая сортировка в Python

Вот довольно компактная реализация быстрой сортировки:

from random import randint

def quicksort(array):
    # Если входной массив содержит менее двух элементов,
    # затем вернуть его как результат функции
    if len(array) < 2:
        return array

    low, same, high = [], [], []

    # Выберите свой элемент `pivot` случайным образом
    pivot = array[randint(0, len(array) - 1)]

    for item in array:
        # Элементы, которые меньше, чем `pivot`, переходят в
        # список `low`. Элементы, размер которых превышает
        # `pivot` перейти в список` high`. Элементы, которые
        # равно `pivot` перейти к списку` same`.
        if item < pivot:
            low.append(item)
        elif item == pivot:
            same.append(item)
        elif item > pivot:
            high.append(item)

    # Окончательный результат объединяет отсортированный `low` список
    # с тем же списком и отсортированным списком `high`
    return quicksort(low) + same + quicksort(high)

Вот краткое изложение кода:

• Строка 6 останавливает рекурсивную функцию, если массив содержит менее двух элементов.
• Строка 12 выбирает pivot элемент случайным образом из списка и переходит к разбиению списка.
• Строки и 20 помещают каждый элемент, который меньше, чем pivot в названный список low.
• Строки и 22 помещают каждый элемент, который равен pivot в названном списке same.
• Строки и 24 помещают каждый элемент, который больше, чем pivot в названный список high.
• Строка рекурсивно сортирует low и high списки и объединяет их вместе с содержимым same списка.

Вот иллюстрация шагов, которые выполняет быстрая сортировка для сортировки массива [8, 2, 6, 4, 5] :

Желтые линии представляют собой разбиение массива на три списка: low, same и high. Зеленые линии представляют сортировку и объединение этих списков. Вот краткое объяснение шагов:

1. pivot Элемент выбирается случайным образом. В этом случае pivot есть 6.
2. Первый проход разделяет входной массив так, чтобы он low содержал [2, 4, 5], same содержал [6] и high содержал [8].
3. quicksort() затем вызывается рекурсивно с в low качестве его ввода. Это выбирает случайное pivot и разбивает массив на [2] как low, [4] как same и [5] как high.
4. Процесс продолжается, но на данный момент оба low и high имеют менее двух элементов каждый. Это завершает рекурсию, и функция снова собирает массив. Добавление отсортированного low и high с любой стороны same списка производит [2, 4, 5].
5. С другой стороны, high список, содержащий [8] менее двух элементов, поэтому алгоритм возвращает отсортированный low массив, который сейчас есть [2, 4, 5]. Слияние с same ( [6] ) и high ( [8] ) создает окончательный отсортированный список.

Выбор pivot элемента

Почему реализация выше выбирает pivot элемент случайным образом? Разве не было бы одинаково последовательно выбирать первый или последний элемент списка ввода? Из-за того, как работает алгоритм быстрой сортировки, количество уровней рекурсии зависит от того, где pivot заканчивается каждый раздел. В лучшем случае алгоритм последовательно выбирает медианный элемент как pivot. Это сделало бы каждую сгенерированную подзадачу ровно в два раза меньше предыдущей проблемы, что привело бы к максимальному уровню log ₂ n. С другой стороны, если алгоритм последовательно выбирает либо наименьший, либо наибольший элемент массива как pivot, то сгенерированные разделы будут настолько неравными, насколько это возможно, что приведет к n-1 уровням рекурсии. Это был бы худший вариант для быстрой сортировки. Как видите, эффективность быстрой сортировки часто зависит от pivot выбора. Если входной массив не отсортирован, то использование первого или последнего элемента в качестве pivot будет работать так же, как случайный элемент. Но если входной массив отсортирован или почти отсортирован, использование первого или последнего элемента pivot может привести к наихудшему сценарию. pivot Случайный выбор повышает вероятность того, что быстрая сортировка выберет значение ближе к медиане и завершится быстрее. Другой вариант выбора pivot - найти медианное значение массива и заставить алгоритм использовать его в качестве pivot. Это можно сделать за O(n) раз. Хотя процесс немного сложнее, использование медианного значения в качестве pivot быстрой сортировки гарантирует, что у вас будет наилучший сценарий "О"‑большое.

Оценка сложности "О"‑большое быстрой сортировки

При быстрой сортировке входной список разбивается на линейное время O(n), и этот процесс рекурсивно повторяется в среднем по журналу ₂ n раз. Это приводит к окончательной сложности O(n \log{n}). Тем не менее, помните обсуждение о том, как выбор pivot влияет на время выполнения алгоритма. Сценарий наилучшего случая O(n) происходит, когда выбранное значение pivot близко к медиане массива, а сценарий O(n^2) происходит, когда pivot наименьшее или наибольшее значение массива. Теоретически, если алгоритм сначала фокусируется на поиске медианного значения, а затем использует его в качестве pivot элемента, то сложность в худшем случае снизится до O(n \log{n}). Медиана массива может быть найдена за линейное время, и, используя ее в качестве pivot гарантии, часть кода быстрой сортировки выполнит за O(n \log{n}). Используя медианное значение в качестве pivot, вы получите конечное время выполнения O (n) + O (n log ₂ n). Вы можете упростить это до O (n log ₂ n), поскольку логарифмическая часть растет намного быстрее, чем линейная часть.

Оценка времени выполнения быстрой сортировки

К настоящему времени вы знакомы с процессом определения времени выполнения алгоритма. Просто измените название алгоритма в строке 8 :

if __name__ == "__main__":
    # Сгенерировать массив элементов ARRAY_LENGTH, состоящий из
    # случайных целочисленных значений от 0 до 999
    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]

    # Вызываем функцию по имени алгоритма сортировки
    # и только что созданный массив
    run_sorting_algorithm(algorithm="quicksort", array=array)

Вы можете выполнить скрипт так же, как раньше:

$ python sorting.py
Algorithm: quicksort. Minimum execution time: 0.11675417600002902

Мало того, что быстрая сортировка завершается менее чем за одну секунду, она также намного быстрее сортировки слиянием ( 0.11 секунды против 0.61 секунд). Увеличение количества элементов, указанных ARRAY_LENGTH в 10,000 к 1,000,000 и запустить скрипт снова заканчивается сортировка слиянием окончания в 97 секундах, в то время как быстрая сортировка сортирует список в считанные 10 секунды.

Преимущества и недостатки быстрой сортировки

Как следует из названия, быстрая сортировка очень быстрая. Хотя в худшем случае это теоретически O(n^2), на практике хорошая реализация быстрой сортировки превосходит большинство других реализаций сортировки. Также, как и сортировка слиянием, быстрая сортировка проста для распараллеливания. Одним из основных недостатков быстрой сортировки является отсутствие гарантии того, что он достигнет средней сложности выполнения. Хотя наихудшие сценарии встречаются редко, некоторые приложения не могут позволить себе рисковать низкой производительностью, поэтому они выбирают алгоритмы, которые остаются в пределах O(n \log{n}) независимо от входных данных. Так же, как сортировка слиянием, быстрая сортировка также заменяет пространство памяти для скорости. Это может стать ограничением для сортировки больших списков. Быстрый эксперимент по сортировке списка из десяти элементов приводит к следующим результатам:

Algorithm: bubble_sort. Minimum execution time: 0.0000909000000000014
Algorithm: insertion_sort. Minimum execution time: 0.00006681900000000268
Algorithm: quicksort. Minimum execution time: 0.0001319930000000004

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

Алгоритм Timsort в Python

Timsort алгоритм считается гибридным алгоритм сортировки, поскольку он использует лучшие в обоих миров сочетание вставки сортировки и сортировки слиянием. Timsort является близким и дорогим сообществу Python, потому что он был создан Тимом Питерсом в 2002 году для использования в качестве стандартного алгоритма сортировки языка Python. Главная особенность Timsort заключается в том, что он использует преимущества уже отсортированных элементов, которые существуют в большинстве реальных наборов данных. Это называется естественным бегом. Затем алгоритм перебирает список, собирая элементы в прогоны и объединяя их в один отсортированный список.

Реализация Timsort в Python

В этом разделе вы создадите базовую реализацию Python, которая иллюстрирует все части алгоритма Timsort. Если вы заинтересованы, вы можете также проверить первоначальную реализацию C в Timsort. Первым шагом в реализации Timsort является изменение реализации insertion_sort() ранее:

def insertion_sort(array, left=0, right=None):
    if right is None:
        right = len(array) - 1

    # Цикл от элемента, обозначенного
    # `left` до элемента, обозначенного` right`
    for i in range(left + 1, right + 1):
        # Это элемент, который мы хотим разместить в
        # правильное место
        key_item = array[i]

       # Инициализировать переменную, которая будет использоваться для
        # найти правильную позицию указанного элемента
        # by `key_item`
        j = i - 1

        # Просмотрите список элементов (слева
        # часть массива) и найдите правильную позицию
        # элемента, на который ссылается `key_item`. Сделай это только
        # если `key_item` меньше, чем соседние значения.
        while j >= left and array[j] > key_item:
            # Сдвинуть значение на одну позицию влево
            # и переместите `j`, чтобы указать на следующий элемент
            # (справа налево)
            array[j + 1] = array[j]
            j -= 1

        # Когда вы закончите сдвигать элементы, установите
        # `key_item` в правильном месте
        array[j + 1] = key_item

    return array

Эта измененная реализация добавляет пару параметров, left и right, которые указывают, какая часть массива должна быть отсортирована. Это позволяет алгоритму Timsort сортировать часть массива на месте. Изменение функции вместо создания новой означает, что ее можно использовать как для сортировки вставкой, так и для Timsort. Теперь посмотрим на реализацию Timsort:

def timsort(array):
    min_run = 32
    n = len(array)

    # Начните с нарезки и сортировки небольших порций
    # входной массив. Размер этих срезов определяется
    # размер вашего `min_run`.
    for i in range(0, n, min_run):
        insertion_sort(array, i, min((i + min_run - 1), n - 1))

    # Теперь вы можете начать объединение отсортированных фрагментов.
    # Начать с min_run, увеличивая размер вдвое
    # каждую итерацию, пока вы не превысите длину
    # массив.
    size = min_run
    while size < n:
        # Определить массивы, которые будут
        # быть объединенными
        for start in range(0, n, size * 2):
            # Вычислить среднюю точку (где заканчивается первый массив
            # и второй запуск) и ʻendpoint` (где
            # второй массив заканчивается)
            midpoint = start + size - 1
            end = min((start + size * 2 - 1), (n-1))

            # Объединить два подмассива.
            # Массив `left` должен идти от` start` до
            # `midpoint + 1`, а массив` right` должен
            # перейти от `midpoint + 1` к ʻend + 1`.
            merged_array = merge(
                left=array[start:midpoint + 1],
                right=array[midpoint + 1:end + 1])

            # Наконец, поместите объединенный массив обратно в
            # ваш массив
            array[start:start + len(merged_array)] = merged_array

        # Каждая итерация должна удваивать размер ваших массивов
        size *= 2

    return array

Хотя реализация немного сложнее, чем предыдущие алгоритмы, мы можем кратко изложить ее следующим образом:

• Строкии 9 создают небольшие фрагменты или серии массивов и сортируют их с использованием сортировки вставками. Ранее вы узнали, что сортировка вставкой выполняется быстро в небольших списках, и Timsort этим пользуется. Timsort использует недавно введенные параметры left и right параметры insertion_sort() для сортировки списка без необходимости создавать новые массивы, такие как сортировка слиянием и быстрая сортировка.
• Строка 16 объединяет эти меньшие серии, причем каждый цикл 32 изначально имеет размер. С каждой итерацией размер прогонов удваивается, и алгоритм продолжает объединять эти более крупные прогоны, пока не останется один отсортированный прогон.

Обратите внимание, что, в отличие от сортировки слиянием, Timsort объединяет подмассивы, которые были отсортированы ранее. Это уменьшает общее количество сравнений, необходимых для создания отсортированного списка. Это преимущество перед сортировкой слиянием станет очевидным при проведении экспериментов с использованием разных массивов. Наконец, строка 2 определяет min_run = 32. Здесь есть две причины для использования 32 в качестве значения:

1. Сортировка небольших массивов с использованием сортировки вставкой выполняется очень быстро и min_run имеет небольшое значение, чтобы воспользоваться этой характеристикой. Инициализация min_run со значением, которое слишком велико, устранит цель использования сортировки вставкой и замедлит алгоритм.
2. Объединение двух сбалансированных списков намного эффективнее, чем объединение списков непропорционального размера. Выбор min_run значения, равного степени двух, обеспечивает лучшую производительность при объединении всех различных прогонов, которые создает алгоритм.

Комбинируя оба условия выше предлагает несколько вариантов min_run. Реализация в этом руководстве использует в min_run = 32 качестве одной из возможностей.

Оценка сложности "О"‑большое Timsort

В среднем сложность Timsort равна O(n \log{n}), так же как сортировка слиянием и быстрая сортировка. Логарифмическая часть получается из удвоения размера прогона для выполнения каждой операции линейного слияния. Однако Timsort работает исключительно хорошо в уже отсортированных или близких к спискам списках, что приводит к наилучшему сценарию O(n). В этом случае Timsort явно превосходит сортировку слиянием и соответствует наилучшему сценарию для быстрой сортировки. Но худшим случаем для Timsort также является O(n \log{n}), который превосходит O быстрой сортировки (n ² ).

Оценка времени выполнения Timsort

Вы можете использовать, run_sorting_algorithm() чтобы увидеть, как Timsort выполняет сортировку массива из десяти тысяч элементов:

if __name__ == "__main__":
    # Сгенерировать массив элементов ARRAY_LENGTH, состоящий из
    # случайных целочисленных значений от 0 до 999
    array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]

    # Вызываем функцию по имени алгоритма сортировки
    # и только что созданный массив
    run_sorting_algorithm(algorithm="timsort", array=array)

Теперь выполните скрипт, чтобы получить время выполнения timsort :

$ python sorting.py
Algorithm: timsort. Minimum execution time: 0.5121690789999998

В 0.51 считанные секунды эта реализация Timsort на полные 0.1 секунды, или на процентов, быстрее сортировки слиянием, хотя и не соответствует 0.11 быстрой сортировке. Это также на 000 процентов быстрее, чем сортировка вставок! Теперь попробуйте отсортировать уже отсортированный список, используя эти четыре алгоритма, и посмотрите, что произойдет. Вы можете изменить свой __main__ раздел следующим образом:

if __name__ == "__main__":
    # Generate a sorted array of ARRAY_LENGTH items
    array = [i for i in range(ARRAY_LENGTH)]

    # Call each of the functions
    run_sorting_algorithm(algorithm="insertion_sort", array=array)
    run_sorting_algorithm(algorithm="merge_sort", array=array)
    run_sorting_algorithm(algorithm="quicksort", array=array)
    run_sorting_algorithm(algorithm="timsort", array=array)

Если вы сейчас выполните скрипт, то все алгоритмы будут запущены и выведут соответствующее время выполнения:

Algorithm: insertion_sort. Minimum execution time: 53.5485634999991
Algorithm: merge_sort. Minimum execution time: 0.372304601
Algorithm: quicksort. Minimum execution time: 0.24626494199999982
Algorithm: timsort. Minimum execution time: 0.23350277099999994

На этот раз Timsort набирает на тридцать семь процентов быстрее, чем сортировка слиянием, и на пять процентов быстрее, чем быстрая сортировка, что позволяет ему использовать преимущества уже отсортированных прогонов. Обратите внимание, что Timsort извлекает выгоду из двух алгоритмов, которые работают намного медленнее, чем сами по себе. Гений Timsort заключается в объединении этих алгоритмов и использовании их сильных сторон для достижения впечатляющих результатов.

Преимущества и недостатки Timsort

Основным недостатком Timsort является его сложность. Несмотря на реализацию очень упрощенной версии исходного алгоритма, он все еще требует гораздо больше кода, потому что он опирается как на, так insertion_sort() и на merge(). Одним из преимуществ Timsort является его способность предсказуемо выполнять за O(n \log{n}) независимо от структуры входного массива. Сравните это с быстрой сортировкой, которая может ухудшиться до O(n^2). Timsort также очень быстр для небольших массивов, потому что алгоритм превращается в одну сортировку вставки. Для реального использования, в котором обычно сортируются массивы, уже имеющие некоторый ранее существующий порядок, Timsort является отличным вариантом. Его адаптивность делает его отличным выбором для сортировки массивов любой длины.

Заключение

Сортировка является важным инструментом в любом наборе инструментов Pythonista. Обладая знаниями о различных алгоритмах сортировки в Python и о том, как максимально использовать их потенциал, вы готовы внедрять более быстрые и эффективные приложения и программы! В этом уроке вы узнали:

• Как встроенный Python sort() работает за кулисами
• Что такое обозначение "О"‑большое и как его использовать для сравнения эффективности различных алгоритмов
• Как измерить фактическое время, потраченное на выполнение вашего кода
• Как реализовать пять разных алгоритмов сортировки в Python
• В чем плюсы и минусы использования разных алгоритмов

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

По мотивам: Real Python