Реализация алгоритма сортировки на языке программирования python

Смотрите сейчас Этот учебник имеет связанный с ним видеокурс. Созданный командой Real Python. Посмотрите его вместе с письменным учебником. Чтобы углубить свое понимание: Введение в алгоритмы сортировки в Python

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

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

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

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

Давайте начнем!

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

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

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

  • Поиск: Поиск элемента в списке работает намного быстрее. Если список отсортирован.

  • Выбор: Выбор элементов из списка на основе их отношения к остальным элементам проще с помощью отсортированных данных.

    Например, найти k-самое большое или самое маленькое значение или найти медианное значение списка гораздо проще. Когда значения расположены в порядке возрастания или убывания.

  • Дубликаты: Поиск повторяющихся значений в списке может быть выполнен очень быстро. Когда список отсортирован.

  • Распределение: Анализ частотного распределения элементов в списке выполняется очень быстро. Если список отсортирован. Например, найти элемент. Который появляется чаще или реже всего. Относительно просто с помощью отсортированного списка.

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

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

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

>>>

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

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

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

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

выполнения алгоритмов сортировки:

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

Хронометраж Вашего Кода

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

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

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

 1from random import randint  2from timeit import repeat  3  4def run_sorting_algorithm(algorithm, array):  5 # Set up the context and prepare the call to the specified  6 # algorithm using the supplied array. Only import the  7 # algorithm function if it's not the built-in `sorted()`.  8 setup_code = f"from __main__ import {algorithm}" \  9 if algorithm != "sorted" else "" 10 11 stmt = f"{algorithm}({array})" 12 13 # Execute the code ten different times and return the time 14 # in seconds that each execution took 15 times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10) 16 17 # Finally. Display the name of the algorithm and the 18 # minimum time it took to run 19 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():

21ARRAY_LENGTH = 10000 22 23if __name__ == "__main__": 24 # Generate an array of `ARRAY_LENGTH` items consisting 25 # of random integer values between 0 and 999 26 array = [randint(0, 1000) for i in range(ARRAY_LENGTH)] 27 28 # Call the function using the name of the sorting algorithm 29 # and the array you just created 30 run_sorting_algorithm(algorithm="sorted", array=array) 

Если вы сохраните приведенный выше код в

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

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

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

Измерение Эффективности С Помощью Нотации Big O

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

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

Предполагая. Что n-это размер входных данных алгоритма. Обозначение Big O представляет собой отношение между n и количеством шагов. Которые алгоритм предпринимает для поиска решения. Big O использует заглавную букву “O”. За которой следует это отношение в круглых скобках. Например, O(n) представляет алгоритмы. Которые выполняют ряд шагов. Пропорциональных размеру их входных данных.

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

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

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

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

Пузырьковая сортировка-один из самых простых алгоритмов сортировки. Его название происходит от того. Как работает алгоритм: с каждым новым проходом самый большой элемент в списке “всплывает” к своему правильному положению.

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

Реализация пузырьковой сортировки в Python

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

 1def bubble_sort(array):  2 n = len(array)  3  4 for i in range(n):  5 # Create a flag that will allow the function to  6 # terminate early if there's nothing left to sort  7 already_sorted = True  8  9 # Start looking at each item of the list one by one, 10 # comparing it with its adjacent value. With each 11 # iteration, the portion of the array that you look at 12 # shrinks because the remaining items have already been 13 # sorted. 14 for j in range(n - i - 1): 15 if array[j] > array[j + 1]: 16 # If the item you're looking at is greater than its 17 # adjacent value, then swap them 18 array[j], array[j + 1] = array[j + 1], array[j] 19 20 # Since you had to swap two elements, 21 # set the `already_sorted` flag to `False` so the 22 # algorithm doesn't finish prematurely 23 already_sorted = False 24 25 # If there were no swaps during the last iteration, 26 # the array is already sorted. And you can terminate 27 if already_sorted: 28 break 29 30 return array 

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

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

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

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

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

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

Измерительная сложность пузырьковой сортировки Big O Runtime

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

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

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

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

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

Хронометраж Реализации Пузырьковой Сортировки

Используя ваш run_sorting_algorithm()пример из предыдущего урока, вот время. Необходимое для пузырьковой сортировки для обработки массива с десятью тысячами элементов. Строка 8 заменяет название алгоритма. А все остальное остается прежним:

 1if __name__ == "__main__":  2 # Generate an array of `ARRAY_LENGTH` items consisting  3 # of random integer values between 0 and 999  4 array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]  5  6 # Call the function using the name of the sorting algorithm  7 # and the array you just created  8 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нескольких секунд для запуска. Предполагая. Что у вас есть аналогичные аппаратные характеристики. Более медленные машины могут занять гораздо больше времени. Чтобы закончить.

Анализ сильных и слабых сторон Bubble Sort

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

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

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

Как и пузырьковая сортировка, алгоритм сортировки вставки прост в реализации и понимании. Но в отличие от пузырьковой сортировки. Он строит сортированный список по одному элементу за раз. Сравнивая каждый элемент с остальной частью списка и вставляя его в правильное положение. Эта процедура “вставки” дает алгоритму его имя.

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

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

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

 1def insertion_sort(array):  2 # Loop from the second element of the array until  3 # the last element  4 for i in range(1, len(array)):  5 # This is the element we want to position in its  6 # correct place  7 key_item = array[i]  8  9 # Initialize the variable that will be used to 10 # find the correct position of the element referenced 11 # by `key_item` 12 j = i - 1 13 14 # Run through the list of items (the left 15 # portion of the array) and find the correct position 16 # of the element referenced by `key_item`. Do this only 17 # if `key_item` is smaller than its adjacent values. 18 while j >= 0 and array[j] > key_item: 19 # Shift the value one position to the left 20 # and reposition j to point to the next element 21 # (from right to left) 22 array[j + 1] = array[j] 23 j -= 1 24 25 # When you finish shifting the elements. You can position 26 # `key_item` in its correct location 27 array[j + 1] = key_item 28 29 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, 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в правильное место. Оставляя массив отсортированным.

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

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

Наихудший случай происходит. Когда поставляемый массив сортируется в обратном порядке. В этом случае внутренний цикл должен выполнить каждое сравнение. Чтобы поместить каждый элемент в правильное положение. Это все еще дает вам сложность выполнения O(n2).

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

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

Хронометраж Реализации Сортировки Вставки

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

 1if __name__ == "__main__":  2 # Generate an array of `ARRAY_LENGTH` items consisting  3 # of random integer values between 0 and 999  4 array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]  5  6 # Call the function using the name of the sorting algorithm  7 # and the array we just created  8 run_sorting_algorithm(algorithm="insertion_sort", array=array) 

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

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

Обратите внимание. Что реализация сортировки вставки заняла примерно 17меньше секунд. Чем реализация пузырьковой сортировки для сортировки того же массива. Несмотря на то. Что они оба являются алгоритмами O(n2), сортировка вставки более эффективна.

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

Как и пузырьковая сортировка. Алгоритм сортировки вставки очень прост в реализации. Несмотря на то. Что сортировка вставки является алгоритмом O(n2), на практике она также гораздо более эффективна. Чем другие квадратичные реализации. Такие как пузырьковая сортировка.

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

Тем не менее. Сортировка вставки непрактична для больших массивов. Открывая дверь алгоритмам. Которые могут масштабироваться более эффективными способами.

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

Сортировка слиянием — это очень эффективный алгоритм сортировки. Он основан на подходе

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

Алгоритмы

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

В случае сортировки слиянием подход

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

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

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

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

 1def merge(left, right):  2 # If the first array is empty. Then nothing needs  3 # to be merged. And you can return the second array as the result  4 if len(left) == 0:  5 return right  6  7 # If the second array is empty. Then nothing needs  8 # to be merged. And you can return the first array as the result  9 if len(right) == 0: 10 return left 11 12 result = [] 13 index_left = index_right = 0 14 15 # Now go through both arrays until all the elements 16 # make it into the resultant array 17 while len(result)  len(left) + len(right): 18 # The elements need to be sorted to add them to the 19 # resultant array. So you need to decide whether to get 20 # the next element from the first or the second array 21 if left[index_left]  right[index_right]: 22 result.append(left[index_left]) 23 index_left += 1 24 else: 25 result.append(right[index_right]) 26 index_right += 1 27 28 # If you reach the end of either array. Then you can 29 # add the remaining elements from the other array to 30 # the result and break the loop 31 if index_right == len(right): 32 result += left[index_left:] 33 break 34 35 if index_left == len(left): 36 result += right[index_right:] 37 break 38 39 return result 

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

  • Строки 4 и 9 проверяют. Является ли какой-либо из массивов пустым. Если один из них есть. То объединять нечего. Поэтому функция возвращает другой массив.

  • Строка 17 запускает whileцикл, который заканчивается всякий раз. Когда результат содержит все элементы из обоих предоставленных массивов. Цель состоит в том. Чтобы заглянуть в оба массива и объединить их элементы для получения отсортированного списка.

  • Строка 21 сравнивает элементы в начале обоих массивов. Выбирает меньшее значение и добавляет его в конец результирующего массива.

  • Строки 31 и 35 добавляют все оставшиеся элементы к результату. Если все элементы из любого из массивов уже были использованы.

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

41def merge_sort(array): 42 # If the input array contains fewer than two elements, 43 # then return it as the result of the function 44 if len(array)  2: 45 return array 46 47 midpoint = len(array) // 2 48 49 # Sort the array by recursively splitting the input 50 # into two equal halves, sorting each half and merging them 51 # together into the final result 52 return merge( 53 left=merge_sort(array[:midpoint]), 54 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()каждую половину. Поскольку массив делится пополам до тех пор. Пока не останется один элемент. Общее число операций деления пополам. Выполняемых этой функцией. Составляет log2n. Поскольку merge()вызывается для каждой половины. Мы получаем общее время выполнения O(n log2n).

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

Выбор Времени Реализации Сортировки Слиянием

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

 1if __name__ == "__main__":  2 # Generate an array of `ARRAY_LENGTH` items consisting  3 # of random integer values between 0 and 999  4 array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]  5  6 # Call the function using the name of the sorting algorithm  7 # and the array you just created  8 run_sorting_algorithm(algorithm="merge_sort", array=array) 

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

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

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

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

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

Тем не менее. Для небольших списков временные затраты на рекурсию позволяют таким алгоритмам. Как сортировка пузырьков и сортировка вставок. Работать быстрее. Например, выполнение эксперимента со списком из десяти элементов приводит к следующим результатам:

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

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

Вот довольно компактная реализация Quicksort:

 1from random import randint  2  3def quicksort(array):  4 # If the input array contains fewer than two elements,  5 # then return it as the result of the function  6 if len(array)  2:  7 return array  8  9 low, same, high = [], [], [] 10 11 # Select your `pivot` element randomly 12 pivot = array[randint(0, len(array) - 1)] 13 14 for item in array: 15 # Elements that are smaller than the `pivot` go to 16 # the `low` list. Elements that are larger than 17 # `pivot` go to the `high` list. Elements that are 18 # equal to `pivot` go to the `same` list. 19 if item  pivot: 20 low.append(item) 21 elif item == pivot: 22 same.append(item) 23 elif item > pivot: 24 high.append(item) 25 26 # The final result combines the sorted `low` list 27 # with the `same` list and the sorted `high` list 28 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списка.

Вот иллюстрация шагов. Которые Quicksort выполняет для сортировки массива[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]as low, [4]as sameи [5]as 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. Это сделало бы каждую сгенерированную подзадачу ровно вдвое меньше предыдущей задачи. Что привело бы не более чем к логарифмическим2n уровням.

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

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

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

Измерение Большой O Сложности Quicksort

С помощью Quicksort входной список секционируется в линейном времени O(n), и этот процесс рекурсивно повторяется в среднем log2n раз. Это приводит к конечной сложности O(n log2n).

Тем не менее. Вспомните дискуссию о том. Как выбор pivotвлияет на время выполнения алгоритма. Наилучший сценарий O(n) происходит. Когда выбранное значение pivotблизко к медиане массива. А сценарий O(n2)-когда pivotнаименьшее или наибольшее значение массива.

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

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

Примечание: Хотя достижение O(n log2n) возможно в наихудшем сценарии Quicksort. Этот подход редко используется на практике. Списки должны быть довольно большими. Чтобы реализация была быстрее. Чем простой рандомизированный выбор pivot.

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

Сроки Реализации Quicksort

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

 1if __name__ == "__main__":  2 # Generate an array of `ARRAY_LENGTH` items consisting  3 # of random integer values between 0 and 999  4 array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]  5  6 # Call the function using the name of the sorting algorithm  7 # and the array you just created  8 run_sorting_algorithm(algorithm="quicksort", array=array) 

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

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

Быстрая сортировка не только завершается менее чем за одну секунду. Но и намного быстрее. Чем сортировка слиянием (0.11 секунды против 0.61секунд). Увеличение количества элементов, заданных ARRAY_LENGTHпараметром from 10,000to1,000,000, и повторный запуск скрипта приводят к тому. Что сортировка слиянием завершается за 97считанные секунды. В то время как Quicksort сортирует список всего за несколько 10секунд.

Анализ сильных и слабых сторон Quicksort

Верный своему названию. Quicksort очень быстр. Хотя его наихудший сценарий теоретически равен O(n2), на практике хорошая реализация Quicksort превосходит большинство других реализаций сортировки. Кроме того. Как и сортировка слиянием. Quicksort легко распараллелить.

Одним из главных недостатков Quicksort является отсутствие гарантии. Что он достигнет средней сложности выполнения. Хотя наихудшие сценарии встречаются редко. Некоторые приложения не могут позволить себе рисковать низкой производительностью. Поэтому они выбирают алгоритмы. Которые остаются в пределах O(n log2n) независимо от входных данных.

Как и сортировка слиянием. Quicksort также обменивает пространство памяти на скорость. Это может стать ограничением для сортировки больших списков.

Быстрый эксперимент сортировка списка из десяти элементов приводит к следующим результатам:

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

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

Алгоритм Timsort в Python

Алгоритм Timsort считается гибридным алгоритмом сортировки. Поскольку он использует лучшую в обоих мирах комбинацию сортировки вставки и сортировки слияния. Timsort близок и дорог сообществу Python. Потому что он был создан Тимом Питерсом в 2002 году для использования в качестве стандартного алгоритма сортировки языка Python.

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

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

В этом разделе вы создадите реализацию barebones Python. Которая иллюстрирует все части алгоритма Timsort. Если вам интересно. Вы также можете проверить оригинальную реализацию Timsort на языке Си.

Первым шагом в реализации Timsort является изменение реализации insertion_sort()from before:

 1def insertion_sort(array, left=0, right=None):  2 if right is None:  3 right = len(array) - 1  4  5 # Loop from the element indicated by  6 # `left` until the element indicated by `right`  7 for i in range(left + 1, right + 1):  8 # This is the element we want to position in its  9 # correct place 10 key_item = array[i] 11 12 # Initialize the variable that will be used to 13 # find the correct position of the element referenced 14 # by `key_item` 15 j = i - 1 16 17 # Run through the list of items (the left 18 # portion of the array) and find the correct position 19 # of the element referenced by `key_item`. Do this only 20 # if the `key_item` is smaller than its adjacent values. 21 while j >= left and array[j] > key_item: 22 # Shift the value one position to the left 23 # and reposition `j` to point to the next element 24 # (from right to left) 25 array[j + 1] = array[j] 26 j -= 1 27 28 # When you finish shifting the elements. Position 29 # the `key_item` in its correct location 30 array[j + 1] = key_item 31 32 return array 

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

Теперь взгляните на реализацию Timsort:

 1def timsort(array):  2 min_run = 32  3 n = len(array)  4  5 # Start by slicing and sorting small portions of the  6 # input array. The size of these slices is defined by  7 # your `min_run` size.  8 for i in range(0, n, min_run):  9 insertion_sort(array, i, min((i + min_run - 1), n - 1)) 10 11 # Now you can start merging the sorted slices. 12 # Start from `min_run`, doubling the size on 13 # each iteration until you surpass the length of 14 # the array. 15 size = min_run 16 while size  n: 17 # Determine the arrays that will 18 # be merged together 19 for start in range(0, n, size * 2): 20 # Compute the `midpoint` (where the first array ends 21 # and the second starts) and the `endpoint` (where 22 # the second array ends) 23 midpoint = start + size - 1 24 end = min((start + size * 2 - 1), (n-1)) 25 26 # Merge the two subarrays. 27 # The `left` array should go from `start` to 28 # `midpoint + 1`, while the `right` array should 29 # go from `midpoint + 1` to `end + 1`. 30 merged_array = merge( 31 left=array[start:midpoint + 1], 32 right=array[midpoint + 1:end + 1]) 33 34 # Finally. Put the merged array back into 35 # your array 36 array[start:start + len(merged_array)] = merged_array 37 38 # Each iteration should double the size of your arrays 39 size *= 2 40 41 return array 

Хотя реализация немного сложнее. Чем предыдущие алгоритмы. Мы можем быстро суммировать ее следующим образом:

  • Строки 8 и 9 создают небольшие фрагменты или прогоны массива и сортируют их с помощью сортировки вставки. Ранее вы узнали. Что сортировка вставок выполняется быстро в небольших списках. И Timsort использует это преимущество. Timsort использует недавно введенные leftrightпараметры и 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в разделе Computing minrun.

Измерение большой сложности Тимсорта

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

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

Хронометраж Реализации Timsort

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

 1if __name__ == "__main__":  2 # Generate an array of `ARRAY_LENGTH` items consisting  3 # of random integer values between 0 and 999  4 array = [randint(0, 1000) for i in range(ARRAY_LENGTH)]  5  6 # Call the function using the name of the sorting algorithm  7 # and the array you just created  8 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__раздел следующим образом:

 1if __name__ == "__main__":  2 # Generate a sorted array of ARRAY_LENGTH items  3 array = [i for i in range(ARRAY_LENGTH)]  4  5 # Call each of the functions  6 run_sorting_algorithm(algorithm="insertion_sort", array=array)  7 run_sorting_algorithm(algorithm="merge_sort", array=array)  8 run_sorting_algorithm(algorithm="quicksort", array=array)  9 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 приходит на целых тридцать семь процентов быстрее. Чем сортировка слиянием. И на пять процентов быстрее. Чем Quicksort. Используя свою способность использовать преимущества уже отсортированных пробегов.

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

Анализ сильных и слабых сторон Timsort

Основным недостатком Timsort является его сложность. Несмотря на реализацию очень упрощенной версии исходного алгоритма. Он по-прежнему требует гораздо больше кода. Поскольку опирается на оба insertion_sort()и merge().

Одним из преимуществ Timsort является его способность предсказуемо работать в O(n log2n) независимо от структуры входного массива. Сравните это с Quicksort. Который может деградировать до O(n2). Timsort также очень быстр для небольших массивов. Потому что алгоритм превращается в единственную сортировку вставки.

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

Вывод

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

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

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

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

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

Смотрите сейчас Этот учебник имеет связанный с ним видеокурс. Созданный командой Real Python. Посмотрите его вместе с письменным учебником. Чтобы углубить свое понимание: Введение в алгоритмы сортировки в Python