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

25 апреля, 2020

Подписывайся на наш канал в Telegram, чтобы ежедневно совершенствоваться в Python. Там выходят задачи, полезные советы и сливы платных курсов - перейти

Перевод статьи

Оглавление

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

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

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

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

Важность алгоритмов сортировки в Python

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

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

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

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

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

Язык Python, как и многие другие языки программирования высокого уровня, предлагает возможность сортировки данных из коробки с помощью sorted(). Вот пример сортировки целочисленного массива:>>>

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

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

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

Значение сложности времени

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

  1. Для практической точки зрения вы будете измерять время выполнения реализаций с помощью timeit модуля.
  2. Для более теоретической точки зрения, вы будете измерять время выполнения сложность алгоритмов с использованием Big O нотации .

Время вашего кода

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

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

Вот функция, которую вы можете использовать для определения времени ваших алгоритмов:

from random import randint
from timeit import repeat

def run_sorting_algorithm(algorithm, array):
    # Set up the context and prepare the call to the specified
    # algorithm using the supplied array. Only import the
    # algorithm function if it's not the built-in `sorted()`.
    setup_code = f"from __main__ import {algorithm}" \
        if algorithm != "sorted" else ""

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

    # Execute the code ten different times and return the time
    # in seconds that each execution took
    times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)

    # Finally, display the name of the algorithm and the
    # minimum time it took to run
    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__":
    # 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="sorted", array=array)

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

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

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

Примечание: вы можете узнать больше о timeit модуле в официальной документации Python .

Измерение эффективности с большой нотацией

Конкретного времени, которое требуется алгоритму для запуска, недостаточно, чтобы получить полную картину его временной сложности . Чтобы решить эту проблему, вы можете использовать обозначение Big O (произносится как «большой о»). Big O часто используется для сравнения различных реализаций и определения, какая из них наиболее эффективна, пропуская ненужные детали и концентрируясь на том, что является наиболее важным во время выполнения алгоритма.

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

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

Хотя этот учебник не собирается углубляться в детали нотации Big O, вот пять примеров сложности времени выполнения различных алгоритмов:

Большой ОсложностьОписание
O (1)постояннаяВремя выполнения является постоянным независимо от размера ввода. Поиск элемента в хеш-таблице является примером операции, которая может быть выполнена за постоянное время .
На)линейныйВремя выполнения растет линейно с размером входных данных. Функция, которая проверяет условие для каждого элемента списка, является примером алгоритма O (n) .
O (n 2 )квадратныйВремя выполнения – это квадратичная функция от размера ввода. Наивная реализация поиска повторяющихся значений в списке, в которой каждый элемент должен проверяться дважды, является примером квадратичного алгоритма.
O (2 н )экспоненциальныйВремя выполнения растет в геометрической прогрессии в зависимости от размера ввода. Эти алгоритмы считаются крайне неэффективными. Примером экспоненциального алгоритма является задача трехцветности .
O (log n)логарифмическийВремя выполнения растет линейно, а размер входных данных растет экспоненциально. Например, если для обработки тысячи элементов требуется одна секунда, то для обработки десяти тысяч потребуется две секунды, для обработки ста тысяч – три секунды и так далее. Двоичный поиск является примером логарифмического алгоритма выполнения.

В этом руководстве рассматривается сложность времени выполнения Big O для каждого из обсуждаемых алгоритмов сортировки. Он также включает краткое объяснение того, как определить время выполнения в каждом конкретном случае. Это поможет вам лучше понять, как начать использовать Big O для классификации других алгоритмов.

Примечание. Для более глубокого понимания Big O, а также нескольких практических примеров в Python, ознакомьтесь с примечаниями по Big O и анализом алгоритмов с помощью примеров Python .

Алгоритм пузырьковой сортировки в Python

Bubble Sort – один из самых простых алгоритмов сортировки. Его название происходит от того, как работает алгоритм: с каждым новым проходом самый большой элемент в списке «всплывает» к своей правильной позиции.

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

Реализация Bubble Sort в Python

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

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

    for i in range(n):
        # Start looking at each item of the list one by one,
        # comparing it with its adjacent value. With each
        # iteration, the portion of the array that you look at
        # shrinks because the remaining items have already been
        # sorted.
        for j in range(n - i - 1):
            # Create a flag that will allow the function to
            # terminate early if there's nothing left to sort
            already_sorted = True

            if array[j] > array[j + 1]:
                # If the item you're looking at is greater than its
                # adjacent value, then swap them
                array[j], array[j + 1] = array[j + 1], array[j]

                # Since you had to swap two elements,
                # set the `already_sorted` flag to `False` so the
                # algorithm doesn't finish prematurely
                already_sorted = False

        # If there were no swaps during the last iteration,
        # the array is already sorted, and you can terminate
        if already_sorted:
            break
 
    return array

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

Циклы в строках 4 и 10 определяют способ прохождения алгоритма по списку. Обратите внимание, как j изначально идет от первого элемента в списке к элементу непосредственно перед последним. Во время второй итерации j выполняется до двух элементов из последнего, затем до трех элементов из последнего и т. Д. В конце каждой итерации конечная часть списка будет отсортирована.

По мере прохождения циклов строка 15 сравнивает каждый элемент со смежным значением, а строка 18 меняет их местами, если они находятся в неправильном порядке. Это гарантирует отсортированный список в конце функции.

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

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

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

Алгоритм пузырьковой сортировки
Bubble Sort Process

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

  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и так далее, пока список не будет отсортирован.

Измерение B & B сложности сортировки Bubble Sort

Ваша реализация пузырьковой сортировки состоит из двух вложенных forциклов, в которых алгоритм выполняет n – 1 сравнение, затем n – 2 сравнения и так далее, пока не будет выполнено окончательное сравнение. В итоге получается (n – 1) + (n – 2) + (n – 3) +… + 2 + 1 = n (n-1) / 2 сравнения, которые также можно записать как ½n 2 – ½n ,

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

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

В тех случаях, когда алгоритм получает массив, который уже отсортирован – и при условии, что реализация включает в себя already_sorted оптимизацию флага, описанную ранее, – сложность времени выполнения снизится до гораздо лучшего значения O (n), поскольку алгоритму не нужно будет посещать какой-либо элемент более одного раза ,

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

Сроки реализации Bubble Sort

Используя ваш 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 секунд, при условии, что у вас схожие аппаратные характеристики. Более медленные машины могут занять гораздо больше времени, чтобы закончить.

Анализ сильных и слабых сторон пузырьковой сортировки

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

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

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

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

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

Реализация сортировки вставок в Python

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

def insertion_sort(array):
    # Loop from the second element of the array until
    # the last element
    for i in range(1, len(array)):
        # This is the element we want to position in its
        # correct place
        key_item = array[i]

        # Initialize the variable that will be used to
        # find the correct position of the element referenced
        # by `key_item`
        j = i - 1

        # Run through the list of items (the left
        # portion of the array) and find the correct position
        # of the element referenced by `key_item`. Do this only
        # if `key_item` is smaller than its adjacent values.
        while j >= 0 and array[j] > key_item:
            # Shift the value one position to the left
            # and reposition j to point to the next element
            # (from right to left)
            array[j + 1] = array[j]
            j -= 1

        # When you finish shifting the elements, you can position
        # `key_item` in its correct location
        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.
  • Строка 27 располагается 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 алгоритм сдвигается на 8 вправо. Полученный массив в этой точке [2, 8, 8, 4, 5].
  6. Поскольку 6 > 2 алгоритму не нужно продолжать проходить через подмассив, он позиционирует key_itemи заканчивает второй проход. В это время результирующий массив имеет вид [2, 6, 8, 4, 5].
  7. Третий проход по списку помещает элемент 4в правильное положение, а четвертый проход помещает элемент 5в правильное место, оставляя массив отсортированным.

Измерение сложности ввода типа Big O Runtime

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

Худший случай случается, когда предоставленный массив сортируется в обратном порядке. В этом случае внутренний цикл должен выполнять каждое сравнение, чтобы поместить каждый элемент в правильное положение. Это все еще дает вам O (n 2 ) сложность во время выполнения.

Наилучший случай случается, когда предоставленный массив уже отсортирован. Здесь внутренний цикл никогда не выполняется, что приводит к сложности выполнения O (n) , как в лучшем случае пузырьковой сортировки.

Хотя пузырьковая сортировка и вставка сортировки имеют одинаковую сложность во время выполнения Big O, на практике вставка сортировки значительно эффективнее, чем пузырьковая сортировка. Если вы посмотрите на реализацию обоих алгоритмов, то увидите, как сортировка вставками должна выполнять меньше сравнений для сортировки списка.

Сроки реализации вставки сортировки

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

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 we just created
    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, ознакомьтесь с разделом «Рекурсивное мышление» в Python .

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

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

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

Реализация сортировки слиянием в Python

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

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

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

def merge(left, right):
    # If the first array is empty, then nothing needs
    # to be merged, and you can return the second array as the result
    if len(left) == 0:
        return right

    # If the second array is empty, then nothing needs
    # to be merged, and you can return the first array as the result
    if len(right) == 0:
        return left

    result = []
    index_left = index_right = 0

    # Now go through both arrays until all the elements
    # make it into the resultant array
    while len(result) < len(left) + len(right):
        # The elements need to be sorted to add them to the
        # resultant array, so you need to decide whether to get
        # the next element from the first or the second array
        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 you reach the end of either array, then you can
        # add the remaining elements from the other array to
        # the result and break the loop
        if index_right == len(right):
            result += left[index_left:]
            break

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

    return result

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

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

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

def merge_sort(array):
    # If the input array contains fewer than two elements,
    # then return it as the result of the function
    if len(array) < 2:
       return array

    midpoint = len(array) // 2

    # Sort the array by recursively splitting the input
    # into two equal halves, sorting each half and merging them
    # together into the final result
    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 как 2midpoint Используется для ввода вдвое сократить массив в 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].

Измерение сортировки слияния Big O Сложность

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

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

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

Время реализации сортировки слиянием

Чтобы сравнить скорость сортировки слиянием с двумя предыдущими реализациями, вы можете использовать тот же механизм, что и раньше, и заменить имя алгоритма в строке 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="merge_sort", array=array)

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

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

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

Анализ сильных и слабых сторон сортировки слиянием

Благодаря сложности времени выполнения O (n log 2 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 the input array contains fewer than two elements,
    # then return it as the result of the function
    if len(array) < 2:
        return array

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

    # Select your `pivot` element randomly
    pivot = array[randint(0, len(array) - 1)]

    for item in array:
        # Elements that are smaller than the `pivot` go to
        # the `low` list. Elements that are larger than
        # `pivot` go to the `high` list. Elements that are
        # equal to `pivot` go to the `same` list.
        if item < pivot:
            low.append(item)
        elif item == pivot:
            same.append(item)
        elif item > pivot:
            high.append(item)

    # The final result combines the sorted `low` list
    # with the `same` list and the sorted `high` list
    return quicksort(low) + same + quicksort(high)

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

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

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

Алгоритм быстрой сортировки
Процесс быстрой сортировки

Желтые линии представляют собой разбиение массива на три списка: lowsame и 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 2 n .

С другой стороны, если алгоритм последовательно выбирает либо наименьший, либо наибольший элемент массива как pivot, то сгенерированные разделы будут настолько неравными, насколько это возможно, что приведет к n-1 уровням рекурсии. Это был бы худший вариант для быстрой сортировки.

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

Другой вариант выбора pivot– найти медианное значение массива и заставить алгоритм использовать его в качестве pivot. Это можно сделать за O (n) раз. Хотя процесс немного сложнее, использование медианного значения в качестве pivot быстрой сортировки гарантирует, что у вас будет наилучший сценарий Big O.

Измерение быстрой сложности Big O

При быстрой сортировке входной список разбивается на линейное время O (n) , и этот процесс рекурсивно повторяется в среднем по журналу 2 n раз. Это приводит к окончательной сложности O (n log 2 n) .

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

Теоретически, если алгоритм сначала фокусируется на поиске медианного значения, а затем использует его в качестве pivot элемента, то сложность в худшем случае снизится до O (n log 2 n) . Медиана массива может быть найдена за линейное время, и, используя ее в качестве pivotгарантии, часть кода быстрой сортировки выполнит за O (n log 2 n) .

Используя медианное значение в качестве pivot, вы получите конечное время выполнения O (n) + O (n log 2 n) . Вы можете упростить это до O (n log 2 n), поскольку логарифмическая часть растет намного быстрее, чем линейная часть.

Примечание . Хотя достижение O (n log 2 n) возможно в наихудшем сценарии быстрой сортировки, этот подход редко используется на практике. Списки должны быть достаточно большими, чтобы реализация была быстрее, чем простой случайный выбор pivot.

Случайный выбор pivot делает наихудший случай очень маловероятным. Это делает случайный pivot выбор достаточно хорошим для большинства реализаций алгоритма.

Время реализации быстрой сортировки

К настоящему времени вы знакомы с процессом определения времени выполнения алгоритма. Просто измените название алгоритма в строке 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="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 2 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

    # Loop from the element indicated by
    # `left` until the element indicated by `right`
    for i in range(left + 1, right + 1):
        # This is the element we want to position in its
        # correct place
        key_item = array[i]

        # Initialize the variable that will be used to
        # find the correct position of the element referenced
        # by `key_item`
        j = i - 1

        # Run through the list of items (the left
        # portion of the array) and find the correct position
        # of the element referenced by `key_item`. Do this only
        # if the `key_item` is smaller than its adjacent values.
        while j >= left and array[j] > key_item:
            # Shift the value one position to the left
            # and reposition `j` to point to the next element
            # (from right to left)
            array[j + 1] = array[j]
            j -= 1

        # When you finish shifting the elements, position
        # the `key_item` in its correct location
        array[j + 1] = key_item

    return array

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

Теперь посмотрим на реализацию Timsort:

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

    # Start by slicing and sorting small portions of the
    # input array. The size of these slices is defined by
    # your `min_run` size.
    for i in range(0, n, min_run):
        insertion_sort(array, i, min((i + min_run - 1), n - 1))

    # Now you can start merging the sorted slices.
    # Start from `min_run`, doubling the size on
    # each iteration until you surpass the length of
    # the array.
    size = min_run
    while size < n:
        # Determine the arrays that will
        # be merged together
        for start in range(0, n, size * 2):
            # Compute the `midpoint` (where the first array ends
            # and the second starts) and the `endpoint` (where
            # the second array ends)
            midpoint = start + size - 1
            end = min((start + size * 2 - 1), (n-1))

            # Merge the two subarrays.
            # The `left` array should go from `start` to
            # `midpoint + 1`, while the `right` array should
            # go from `midpoint + 1` to `end + 1`.
            merged_array = merge(
                left=array[start:midpoint + 1],
                right=array[midpoint + 1:end + 1])

            # Finally, put the merged array back into
            # your array
            array[start:start + len(merged_array)] = merged_array

        # Each iteration should double the size of your arrays
        size *= 2

    return array

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

  • Строки 8 и 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 делает что-то более сложное для вычисления min_run. Он выбирает значение от 32 до 64 включительно, так что длина списка, деленного на, min_runв точности равна степени 2. Если это невозможно, выбирается значение, близкое, но строго меньшее, чем степень 2.

Если вам интересно, вы можете прочитать полный анализ того, как выбирать, в min_run разделе « Вычислительная среда ».

Измерение сложности Big O в Timsort

В среднем сложность Timsort равна O (n log 2 n) , так же как сортировка слиянием и быстрая сортировка. Логарифмическая часть получается из удвоения размера прогона для выполнения каждой операции линейного слияния.

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

Сроки вашей реализации Timsort

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

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="timsort", array=array)

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

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

В 0.51считанные секунды эта реализация Timsort на полные 0.1секунды, или на 17 процентов, быстрее сортировки слиянием, хотя и не соответствует 0.11 быстрой сортировке. Это также на 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 2 n) независимо от структуры входного массива. Сравните это с быстрой сортировкой, которая может ухудшиться до O (n 2 ) . Timsort также очень быстр для небольших массивов, потому что алгоритм превращается в одну сортировку вставки.

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

Вывод

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

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

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

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

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


Совершенствуй знания каждый день у нас в Телеграм-каналах

Вопросы, реклама — VK | Telegram