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

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


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

С практической точки зрения, вы будете измерять время выполнения реализаций с помощью модуля timeit.
Для более теоретического ознакомления вы измерите  сложность алгоритмов во время выполнения, используя  Обозначение 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


Помните, что продолжительность каждого эксперимента в секундах частично зависит от используемого вами оборудования, поэтому при запуске кода вы, скорее всего, увидите несколько иные результаты.
 Примечание: Вы можете узнать больше о модуле timeit в официальной документации по Python .
Измерение эффективности с помощью обозначения Big O
определенное время алгоритм выполнения не достаточно информации, чтобы получить полное представление о его временная сложность. Чтобы решить эту проблему, вы можете использовать обозначение Big O (произносится как “большой о”). Big O часто используется для сравнения различных реализаций и принятия решения о том, какая из них наиболее эффективна, пропуская ненужные детали и сосредотачиваясь на том, что наиболее важно во время выполнения алгоритма.
Время в секундах, необходимое для выполнения различных алгоритмов, может зависеть от нескольких не связанных между собой факторов, включая скорость процессора или доступную память. Big O, с другой стороны, предоставляет платформу для выражения сложности выполнения в терминах, не зависящих от аппаратного обеспечения. С помощью Big O вы выражаете сложность в терминах того, насколько быстро увеличивается время выполнения вашего алгоритма по сравнению с размером входных данных, особенно когда входные данные становятся произвольно большими.
Предполагая, что n - это размер входных данных для алгоритма, обозначение большой буквы O представляет соотношение между n и числом количество шагов, которые алгоритм предпринимает для поиска решения. В Big O используется заглавная буква “О”, за которой следует это соотношение в круглых скобках. Например,, O(n) представляет алгоритмы, которые выполняют количество шагов, пропорциональное размеру их входных данных.
Хотя в этом руководстве мы не будем углубляться в детали нотации Big O, вот пять примеров сложности различных алгоритмов во время выполнения:



Big O
Complexity
Description




O(1)
constant
The runtime is constant regardless of the size of the input. Finding an element in a hash table is an example of an operation that can be performed in constant time.


O(n)
linear
The runtime grows linearly with the size of the input. A function that checks a condition on every item of a list is an example of an O(n) algorithm.


O(n2)
quadratic
The runtime is a quadratic function of the size of the input. A naive implementation of finding duplicate values in a list, in which each item has to be checked twice, is an example of a quadratic algorithm.


O(2n)
exponential
The runtime grows exponentially with the size of the input. These algorithms are considered extremely inefficient. An example of an exponential algorithm is the three-coloring problem.


O(log n)
logarithmic
The runtime grows linearly while the size of the input grows exponentially. For example, if it takes one second to process one thousand elements, then it will take two seconds to process ten thousand, three seconds to process one hundred thousand, and so on. Binary search is an example of a logarithmic runtime algorithm.



В этом руководстве описывается большая сложность выполнения каждого из рассмотренных алгоритмов сортировки. В нем также содержится краткое объяснение того, как определить время выполнения в каждом конкретном случае. Это поможет вам лучше понять, как начать использовать Big O для классификации других алгоритмов. 
 Примечание: Для более глубокого понимания Big O, а также нескольких практических примеров в Python ознакомьтесь с Нотацией Big O и анализом алгоритмов на примерах Python.
Алгоритм пузырьковой сортировки в 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() из приведенного выше списка. Вот рисунок, иллюстрирующий, как выглядит массив на каждой итерации алгоритма:

Процесс пузырьковой сортировки
Теперь рассмотрим пошагово, что происходит с массивом по мере выполнения алгоритма:


Код начинается со сравнения первого элемента, 8, с соседним элементом, 2. Начиная с 8 > 2, значения меняются местами, в результате чего получается следующий порядок: [2, 8, 6, 4, 5].


Затем алгоритм сравнивает второй элемент, 8, с соседним элементом, 6. Начиная с 8 > 6, значения меняются местами, в результате чего получается следующий порядок: [2, 6, 8, 4, 5].


Далее алгоритм сравнивает третий элемент, 8, с соседним элементом, 4. Начиная с 8 > 4, он также меняет значения местами, что приводит к следующему порядку: [2, 6, 4, 8, 5].


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


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


Измерение сложности выполнения пузырьковой сортировки Big O
Ваша реализация пузырьковой сортировки состоит из двух вложенных for циклов, в которых алгоритм выполняет n - 1 сравнения, затем n - 2 сравнений и так далее, пока не будет выполнено окончательное сравнение. Это дает в общей сложности (n - 1) + (n - 2) + (n - 3) + ... + 2 + 1 = n(n-1)/2 сравнений, которые также могут быть записаны в виде ½n<плюс>2 - ½n.
Ранее вы узнали, что Big O фокусируется на том, как увеличивается время выполнения по сравнению с размером входных данных. Это означает, что для того, чтобы превратить приведенное выше уравнение в алгоритмическую сложность Big O, вам нужно удалить константы, поскольку они не меняются в зависимости от размера входных данных. 
Это упрощает запись до n<+>2 - 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 секунд, при условии, что у вас аналогичные аппаратные характеристики. На более медленных машинах может потребоваться гораздо больше времени для завершения.
Анализ сильных и слабых сторон пузырьковой сортировки
Основным преимуществом алгоритма пузырьковой сортировки является его простота. Его легко реализовать и понять. Вероятно, это главная причина, по которой в большинстве курсов информатики вводится тема сортировки с использованием пузырьковой сортировки.
Как вы видели ранее, недостатком пузырьковой сортировки является то, что она медленная, а сложность выполнения O(n<<2). К сожалению, это исключает его как практичного кандидата для сортировки больших массивов.
Алгоритм сортировки вставками в 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]:

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


Алгоритм начинается с key_item = 2 и проходит по подмассиву слева от него, чтобы найти для него правильное положение. В этом случае подмассив имеет вид [8].


Начиная с 2 < 8, алгоритм сдвигает элемент 8 на одну позицию вправо. Результирующий массив в этой точке равен [8, 8, 6, 4, 5].


Поскольку в подмассиве больше нет элементов, key_item теперь помещается в его новое положение, и конечный массив выглядит следующим образом: [2, 8, 6, 4, 5].


 Второй проход начинается с key_item = 6 и проходит через подмассив, расположенный слева от него, в данном случае [2, 8].


Начиная с 6 < 8, алгоритм сдвигает значение 8 вправо. Результирующий массив в этой точке равен [2, 8, 8, 4, 5].


Начиная с 6 > 2 алгоритму не нужно постоянно проходить через подмассив, поэтому он помещает key_item и завершает второй проход. В это время результирующий массив будет выглядеть следующим образом [2, 6, 8, 4, 5].


Третий проход по списку помещает элемент 4 в правильное положение, а четвертый проход помещает элемент 5 в правильное место, оставляя массив отсортированным.


Измерение сложности сортировки вставок во время выполнения
Аналогично вашей реализации пузырьковой сортировки, алгоритм сортировки вставкой содержит пару вложенных циклов, которые проходят по списку. Внутренний цикл довольно эффективен, потому что он просматривает список только до тех пор, пока не найдет правильную позицию элемента. Тем не менее, алгоритм по-прежнему имеет  O(n2) сложность выполнения в среднем по случаю.
Наихудший случай возникает, когда предоставленный массив сортируется в обратном порядке. В этом случае внутренний цикл должен выполнять каждое сравнение, чтобы поместить каждый элемент в правильное положение. Это по-прежнему приводит к O(n<<2) сложности во время выполнения.
В лучшем случае это происходит, когда предоставленный массив уже отсортирован. Здесь внутренний цикл никогда не выполняется, что приводит к O(n) сложности во время выполнения, как и в лучшем случае пузырьковой сортировки.
Хотя пузырьковая сортировка и сортировка вставкой имеют одинаковую сложность во время выполнения, на практике сортировка вставкой значительно эффективнее, чем пузырьковая сортировка. Если вы посмотрите на реализацию обоих алгоритмов, то увидите, что сортировка по вставкам требует меньшего количества сравнений для сортировки списка.
Время выполнения сортировки при вставке
Чтобы подтвердить утверждение о том, что сортировка вставкой более эффективна, чем пузырьковая сортировка, вы можете рассчитать время выполнения алгоритма сортировки вставкой и сравнить его с результатами пузырьковой сортировки. Чтобы сделать это, вам просто нужно заменить вызов 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(n<<2>), сортировка вставкой более эффективна.
Анализ сильных и слабых сторон сортировки вставками
Как и пузырьковая сортировка, алгоритм сортировки вставками очень прост в реализации. Несмотря на то, что сортировка вставкой представляет собой алгоритм O(n<<2), на практике он также намного эффективнее других квадратичных реализаций, таких как пузырьковая сортировка.
Существуют более мощные алгоритмы, включая сортировку слиянием и быструю сортировку, но эти реализации являются рекурсивными и обычно не справляются с сортировкой вставкой при работе с небольшими списками. В некоторых реализациях быстрой сортировки даже используется внутренняя сортировка вставкой, если список достаточно мал, чтобы обеспечить более быструю реализацию в целом. Timsort также использует внутреннюю сортировку вставкой для сортировки небольших частей входного массива.
Тем не менее, сортировка вставками непрактична для больших массивов, что открывает путь к алгоритмам, которые могут масштабироваться более эффективными способами.
Алгоритм сортировки слиянием в Python
 Сортировка слиянием - это   очень   эффективный алгоритм сортировки. Он основан на подходе "разделяй и властвуй" - мощном алгоритмическом методе, используемом для решения сложных задач. 
Чтобы правильно понять принцип "разделяй и властвуй", вам следует сначала разобраться с концепцией рекурсии. Рекурсия предполагает разбиение проблемы на более мелкие подзадачи, пока они не станут достаточно маленькими, чтобы с ними можно было справиться. В программировании рекурсия обычно выражается функцией, вызывающей саму себя.
 Примечание: В этом руководстве подробно не рассматривается рекурсия. Чтобы лучше понять, как работает рекурсия, и увидеть ее в действии с помощью Python, ознакомьтесь с Рекурсивное мышление в Python и Рекурсия в Python: введение.
Алгоритмы "разделяй и властвуй" обычно имеют одну и ту же структуру:

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

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

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

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

 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() вступает во владение, объединяя две половины и создавая отсортированный список.
Взгляните на представление шагов, которые merge sort выполняет для сортировки массива [8, 2, 6, 4, 5]:

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


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


Вызов merge_sort() с помощью [8, 2] приводит к появлению [8] и [2]. Процесс повторяется для каждой из этих половин.


Вызов merge_sort() с помощью [8] возвращает [8], поскольку это единственный элемент. То же самое происходит с вызовом merge_sort() с [2].


На этом этапе функция начинает объединять подмассивы обратно, используя merge(), начиная с [8] и [2] в качестве входных массивов, в результате чего получается [2, 8].


С другой стороны, [6, 4, 5] рекурсивно разбивается и объединяется с использованием той же процедуры, в результате чего получается [4, 5, 6].


На заключительном этапе [2, 8] и [4, 5, 6] снова объединяются с merge(), что приводит к окончательному результату: [2, 4, 5, 6, 8].


Измерение сложности сортировки слиянием Big O
Чтобы проанализировать сложность сортировки слиянием, вы можете рассмотреть два ее этапа отдельно:


merge() имеет линейное время выполнения. Он получает два массива, общая длина которых составляет не более n (длина исходного входного массива), и объединяет оба массива, просматривая каждый элемент не более одного раза. Это приводит к сложности выполнения O(n).


Второй шаг рекурсивно разбивает входной массив и вызывает 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
Как и при сортировке слиянием, алгоритм быстрой сортировки использует принцип "разделяй и властвуй" для разделения входного массива на два списка, первый из которых содержит мелкие элементы, а второй - крупные. Затем алгоритм рекурсивно сортирует оба списка до тех пор, пока результирующий список не будет полностью отсортирован.
Разделение входного списка называется  разделением списка. Быстрая сортировка сначала выбирает элемент pivot и разбивает список на pivot, помещая каждый меньший элемент в массив low, а каждый больший элемент в массив high.
Если поместить каждый элемент из списка low слева от списка pivot и каждый элемент из списка high справа, то pivot будет находиться именно там, где он находится. должен быть в окончательном отсортированном списке. Это означает, что теперь функция может рекурсивно применить ту же процедуру к low, а затем к high, пока не будет отсортирован весь список.
Реализация быстрой сортировки в Python
Вот довольно компактная реализация быстрой сортировки:

 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.


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

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


Элемент pivot выбирается случайным образом. В этом случае pivot является 6. 


Первый проход разбивает входной массив таким образом, что low содержит [2, 4, 5], same содержит [6], а high содержит [8].


quicksort() затем вызывается рекурсивно с low в качестве входных данных. При этом выбирается случайный pivot и массив разбивается на [2] как low, [4] как same и [5] как high.


Процесс продолжается, но на данный момент и в low, и в high меньше двух элементов в каждом. На этом рекурсия завершается, и функция снова собирает массив. Добавление отсортированных low и high по обе стороны от списка same приводит к [2, 4, 5].


С другой стороны, список high, содержащий [8], содержит менее двух элементов, поэтому алгоритм возвращает отсортированный массив low, который теперь равен [2, 4, 5]. При объединении его с same ([6]) и high ([8]) получается окончательный отсортированный список.


Выбор элемента pivot
Почему в приведенной выше реализации элемент pivot выбирается случайным образом? Разве не то же самое, если последовательно выбирать первый или последний элемент входного списка?
Из-за того, как работает алгоритм быстрой сортировки, количество уровней рекурсии зависит от того, где pivot заканчивается в каждом разделе. В лучшем случае алгоритм последовательно выбирает элемент медиана в качестве элемента pivot. Это сделало бы каждую сгенерированную подзадачу ровно вдвое меньше предыдущей задачи, что привело бы максимум к логарифмическим<<2n уровням. 
С другой стороны, если алгоритм последовательно выбирает либо наименьший, либо наибольший элемент массива в качестве pivot, то сгенерированные разбиения будут настолько неравными, насколько это возможно, что приведет к n-1 уровни рекурсии. Это был бы наихудший сценарий для быстрой сортировки.
Как вы можете видеть, эффективность быстрой сортировки часто зависит от выбора pivot. Если входной массив несортирован, то использование первого или последнего элемента в качестве pivot будет работать так же, как и со случайным элементом. Но если входной массив отсортирован или почти отсортирован, использование первого или последнего элемента в качестве pivot может привести к наихудшему сценарию. Случайный выбор значения pivot повышает вероятность того, что быстрая сортировка выберет значение, более близкое к среднему значению, и завершит работу быстрее.
Другой вариант выбора pivot заключается в том, чтобы найти среднее значение массива и заставить алгоритм использовать его как pivot. Это можно сделать за  часов  часов. Хотя этот процесс немного сложнее, использование медианного значения в качестве pivot для быстрой сортировки гарантирует, что вы получите наилучший сценарий Big O.
Измерение сложности быстрой сортировки Big O
При быстрой сортировке входной список разбивается на разделы за линейное время, O(n), и этот процесс повторяется рекурсивно в среднем log2n раз. Это приводит к конечной сложности O(n log2n). 
Тем не менее, помните обсуждение того, как выбор параметра pivot влияет на время выполнения алгоритма. Наилучший сценарий O(n) имеет место, когда выбранное значение pivot близко к медиане массива, а значение O(n<<<2) сценарий возникает, когда pivot является наименьшим или наибольшим значением массива.
Теоретически, если алгоритм сначала сосредоточится на поиске медианного значения, а затем использует его в качестве элемента pivot, то сложность в наихудшем случае составит O(n log2n). Медиана массива может быть найдена за линейное время, и ее использование в качестве pivot гарантирует, что часть кода быстрой сортировки будет выполнена за  часов(n логарифмов<<2>n). 
Используя среднее значение в качестве pivot, вы получите конечное время выполнения O(n) + O(n log2n). Вы можете упростить это до O(n log2n), потому что логарифмическая часть растет намного быстрее, чем линейная.
 Примечание: Хотя достижение O(n log2n) возможно в худшем случае быстрой сортировки-в некоторых случаях этот подход редко используется на практике. Списки должны быть достаточно большими, чтобы реализация была более быстрой, чем простой рандомизированный выбор pivot. 
Случайный выбор pivot делает наихудший вариант очень маловероятным. Это делает случайный выбор pivot достаточно хорошим для большинства реализаций алгоритма.
Сроки реализации быстрой сортировки
К настоящему времени вы уже знакомы с процессом определения времени выполнения алгоритма. Просто измените название алгоритма в строке  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, с 10,000 до 1,000,000 и повторный запуск скрипта приводит к завершению сортировки слиянием за 97 секунд, в то время как быстрая сортировка сортирует список всего за 10 секунд.
Анализ сильных и слабых сторон быстрой сортировки
В соответствии со своим названием, функция быстрой сортировки очень быстрая. Хотя теоретически наихудшим сценарием является O(n2), на практике хорошая реализация быстрой сортировки превосходит большинство других реализаций сортировки. Кроме того, как и сортировка слиянием, быстрая сортировка проста в распараллеливании.
Одним из главных недостатков Quicksort является отсутствие гарантии того, что она достигнет средней сложности во время выполнения. Хотя наихудшие сценарии встречаются редко, некоторые приложения не могут позволить себе рисковать низкой производительностью, поэтому они выбирают алгоритмы, которые остаются в пределах O(n log2n) независимо от входных данных.
Как и при сортировке слиянием, при быстрой сортировке объем памяти также увеличивается в пользу скорости. Это может стать ограничением при сортировке больших списков.
Быстрый эксперимент по сортировке списка из десяти элементов приводит к следующим результатам:

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


Результаты показывают, что быстрая сортировка также окупает затраты на рекурсию, когда список достаточно мал, и занимает больше времени, чем сортировка вставкой и пузырьковая сортировка.
Алгоритм временной сортировки в Python
Алгоритм Timsort считается  гибридным алгоритмом   сортировки, поскольку он использует наилучшую из двух возможных комбинацию сортировки вставкой и сортировка слиянием. Timsort близок сообществу Python, потому что он был создан Тимом Питерсом в 2002 году для использования в качестве стандартного алгоритма сортировки языка Python..
 Основной характеристикой Timsort является то, что она использует преимущества уже отсортированных элементов, которые существуют в большинстве реальных наборов данных. Они называются естественными прогонами. Затем алгоритм выполняет итерацию по списку, собирая элементы в прогоны и объединяя их в единый отсортированный список.
Реализация Timsort в Python
В этом разделе вы создадите базовую реализацию на Python, которая иллюстрирует все элементы алгоритма Timsort. Если вам интересно, вы также можете ознакомиться с оригинальной реализацией Timsort на языке Си.
Первым шагом в реализации Timsort является изменение предыдущей реализации insertion_sort():

 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:

 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 использует недавно введенные параметры left и right в insertion_sort() для сортировки списка на месте без необходимости создавать новые массивы, как это делают сортировка слиянием и быстрая сортировка.


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


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


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


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


Сочетание обоих условий, приведенных выше, дает несколько вариантов для min_run. Реализация в этом руководстве использует min_run = 32 в качестве одной из возможностей.
 Примечание: На практике Timsort выполняет несколько более сложные вычисления min_run. Он выбирает значение от 32 до 64 включительно, так что длина списка, деленная на min_run, в точности равна степени 2. Если это невозможно, он выбирает значение, близкое к степени 2, но строго меньшее ее. 
Если вам интересно, вы можете прочитать полный анализ того, как выбрать min_run в соответствии с Минпроцессом вычислений раздел.
Измерение сложности Timsort в Big O
В среднем, сложность временной сортировки составляет O(n log2n), точно так же, как сортировка объединением и быстрая сортировка. Логарифмическая часть заключается в удвоении размера прогона для выполнения каждой операции линейного слияния.
Однако Timsort исключительно хорошо работает с уже отсортированными или почти отсортированными списками, что приводит к наилучшему сценарию O(n). В этом случае Timsort явно превосходит сортировку слиянием и соответствует наилучшему сценарию для быстрой сортировки. Но наихудшим вариантом для 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 работает на целых тридцать семь процентов быстрее, чем сортировка слиянием, и на пять процентов быстрее, чем быстрая сортировка, что позволяет использовать преимущества уже отсортированных прогонов.
Обратите внимание, насколько Timsort выигрывает от двух алгоритмов, которые работают намного медленнее, если использовать их по отдельности. Гениальность Timsort заключается в объединении этих алгоритмов и использовании их сильных сторон для достижения впечатляющих результатов.
Анализ сильных и слабых сторон Timsort
Основным недостатком Timsort является его сложность. Несмотря на реализацию очень упрощенной версии исходного алгоритма, он по-прежнему требует гораздо большего количества кода, поскольку опирается как на insertion_sort(), так и на merge().
Одним из преимуществ Timsort является его способность предсказуемо работать за O(n log2n) независимо от структуры входного массива. Сравните это с быстрой сортировкой, которая может уменьшиться до O(n<<2). Timsort также очень быстр для небольших массивов, поскольку алгоритм сводится к сортировке с помощью одной вставки.
Для использования в реальных условиях, когда обычно сортируют массивы, которые уже имеют определенный порядок, Timsort - отличный вариант. Его адаптивность делает его отличным выбором для сортировки массивов любой длины.
Заключение
Сортировка - важный инструмент в арсенале любого специалиста по Python. Зная различные алгоритмы сортировки в Python и способы максимально использовать их потенциал, вы будете готовы к внедрению более быстрых и эффективных приложений и программной документации!
В этом уроке вы узнали:

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

Вы также узнали о различных методах, таких как рекурсия, разделяй и властвуй и рандомизация. Это фундаментальные строительные блоки для решения длинного списка различных алгоритмов, и они будут возникать снова и снова по мере продолжения исследований.
Воспользуйтесь кодом, представленным в этом руководстве, проведите новые эксперименты и изучите эти алгоритмы подробнее. А еще лучше попробуйте реализовать другие алгоритмы сортировки на Python. Список огромен, но сортировка по выбору,  сортировка по куче и  сортировка по дереву - это три отличных варианта для начала.
<статус завершения article-slug="алгоритмы сортировки-python" class="btn-group mb-0" data-api-article-bookmark-url="/api/v1/статьи/алгоритмы сортировки-python/bookmark/" data-api-article-завершение-статус-url="/api/версия 1/статьи/алгоритмы сортировки-python/завершение_статуса/">



<кнопка поделиться bluesky-text="Интересная статья на #Python от @realpython.com :" email-body="Ознакомьтесь с этой статьей о Python:%0A%0ASorting Algorithms в Python" email-subject="Статья о Python для вас" twitter-text="Интересная статья о Python от @realpython:" url="https://realpython.com/sorting-algorithms-python /" url-title="Алгоритмы сортировки в Python">

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

                







                 Back to Top