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

Вступление

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

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

Quicksort представляет три типа алгоритмов сортировки: разделяй и властвуй , на месте и нестабильный .

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

Это становится важным при сортировке объектов вместо примитивных типов. Например, представьте, что у вас есть несколько объектов Person age , например, Дейв 21 год и Майк 21 год. Если вы использовали быструю сортировку для коллекции, содержащей Дейва и Майка, отсортированных по возрасту, нет гарантии, что Дейв будет появляться перед Майком каждый раз, когда вы запускаете алгоритм, и наоборот.

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

Базовая версия алгоритма делает следующее:

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

Элементы меньшего размера, чем точка поворота, перемещаются влево от точки поворота, а элементы, размер которых превышает размер точки поворота, справа от нее.

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

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

Если у нас есть собственный класс Person , и у каждого человека есть name и age , мы можем отсортировать его по name (лексикографически) или по возрасту (по возрастанию или по убыванию).

Как работает Quicksort

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

Задумайтесь на мгновение - как бы вы выбрали адекватную опору для своего массива? В истории Quicksort было представлено множество идей о том, как выбрать опорный элемент - случайный выбор элемента, который не работает из-за того, насколько «дорогостоящий» выбор случайного элемента, но не гарантирует хорошего выбора опорного элемента; подбор элемента с середины; выбор медианы первого, среднего и последнего элемента; и даже более сложные рекурсивные формулы.

Самый простой подход - просто выбрать первый (или последний) элемент. Как ни странно, это приводит к тому, что Quicksort очень плохо работает с уже отсортированными (или почти отсортированными) массивами.

Именно так большинство людей выбирают реализацию Quicksort, и, поскольку это просто, и такой способ выбора точки поворота является очень эффективной операцией (и нам придется делать это неоднократно), именно этим мы и займемся.

Теперь, когда мы выбрали точку опоры - что нам с ней делать? Опять же, есть несколько способов сделать само разбиение. У нас будет «указатель» на нашу точку поворота, и указатель на «меньшие» элементы, и указатель на «большие» элементы.

Цель состоит в том, чтобы переместить элементы так, чтобы все элементы, меньшие, чем точка поворота, находились слева от него, а все более крупные элементы - справа. Меньшие и большие элементы не обязательно сортируются, мы просто хотим, чтобы они находились на правильной стороне оси поворота. Затем мы рекурсивно перебираем левую и правую стороны поворота.

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

29 представляет первый стержень, низкие точки до 99 и высоких баллов до 44

29 | 99 (низкий) , 27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21, 44 (высокий)

Мы перемещаемся high влево, пока не найдем значение ниже, чем наша точка разворота.

29 | 99 (низкий) , 27,41,66,28,44,78,87,19,31,76,58,88,83,97,12, 21 (высокий) , 44

Теперь, когда наша высокая переменная указывает на 21 , элемент меньше, чем точка поворота, мы хотим найти значение в начале массива, с которым мы можем поменять его местами. Нет никакого смысла менять местами значение, которое также меньше, чем точка поворота, поэтому, если low указывает на меньший элемент, мы пытаемся найти тот, который больше.
Мы перемещаем нашу нижнюю переменную вправо, пока не найдем элемент больше, чем точка поворота . К счастью, нижняя позиция уже была на 99 .
Мы меняем местами низкие и высокие :

29 | 21 (низкий) , 27,41,66,28,44,78,87,19,31,76,58,88,83,97,12, 99 (высокий) , 44

Сразу после этого мы перемещаемся вверх влево и вниз вправо (так как 21 и 99 теперь находятся на своих местах).
Опять же, мы перемещаемся высоко влево, пока не достигнем значения ниже точки разворота , которое мы сразу же находим - 12.
Теперь мы ищем значение больше, чем точка разворота , перемещаясь вниз вправо, и находим первое такое значение на 41

Этот процесс продолжается до тех пор , низких и высоких указателей , наконец , встречаются в одном элементе:

29 | 21,27,12,19, 28 (низкий / высокий) , 44,78,87,66,31,76,58,88,83,97,41,99,44

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

28 , 21,27,12,19, 29 , 44,78,87,66,31,76,58,88,83,97,41,99,44

Как видите, мы добились того, что все значения меньше 29 теперь находятся слева от 29 , а все значения больше 29 - справа.

Затем алгоритм делает то же самое для коллекции 28,21,27,12,19 (левая сторона) и 44,78,87,66,31,76,58,88,83,97,41,99,44 (правая сторона) коллекция.

Выполнение

Сортировка массивов

Быстрая сортировка - это естественно рекурсивный алгоритм: разделите входной массив на более мелкие массивы, переместите элементы в нужную сторону от оси поворота и повторите.

Давайте посмотрим, как будут выглядеть несколько рекурсивных вызовов:

Когда мы впервые вызываем алгоритм, мы рассматриваем все элементы - от индексов 0 до n-1, где n - количество элементов в нашем массиве.
Если бы наша точка поворота оказалась в позиции k , мы бы повторили процесс для элементов от 0 до k-1 и от k + 1 до n-1 .
При сортировке элементов от k + 1 до n-1 текущая точка поворота окажется в некоторой позиции p . Затем мы отсортируем элементы от k + 1 до p-1 и от p + 1 до n-1 и так далее.

При этом мы будем использовать две функции - partition() и quick_sort() . Функция quick_sort() сначала partition() коллекцию, а затем рекурсивно вызовет себя для разделенных частей.

Начнем с функции partition() :

 def partition(array, start, end): 
 pivot = array[start] 
 low = start + 1 
 high = end 
 
 while True: 
 # If the current value we're looking at is larger than the pivot 
 # it's in the right place (right side of pivot) and we can move left, 
 # to the next element. 
 # We also need to make sure we haven't surpassed the low pointer, since that 
 # indicates we have already moved all the elements to their correct side of the pivot 
 while low <= high and array[high] >= pivot: 
 high = high - 1 
 
 # Opposite process of the one above 
 while low <= high and array[low] <= pivot: 
 low = low + 1 
 
 # We either found a value for both high and low that is out of order 
 # or low is higher than high, in which case we exit the loop 
 if low <= high: 
 array[low], array[high] = array[high], array[low] 
 # The loop continues 
 else: 
 # We exit out of the loop 
 break 
 
 array[start], array[high] = array[high], array[start] 
 
 return high

И наконец, реализуем функцию quick_sort()

 def quick_sort(array, start, end): 
 if start >= end: 
 return 
 
 p = partition(array, start, end) 
 quick_sort(array, start, p-1) 
 quick_sort(array, p+1, end)

Когда они оба реализованы, мы можем запустить quick_sort() для простого массива:

 array = [29,99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44] 
 
 quick_sort(array, 0, len(array) - 1) 
 print(array)

Выход:

 [12, 19, 21, 27, 28, 29, 31, 41, 44, 44, 58, 66, 76, 78, 83, 87, 88, 97, 99]

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

Сортировка настраиваемых объектов

Есть несколько способов переписать этот алгоритм для сортировки пользовательских объектов в Python. Очень питоническим способом было бы реализовать операторы сравнения для данного класса, что означает, что нам фактически не нужно менять реализацию алгоритма, поскольку > , == , <= и т. Д. Также будут работать с нашим объектом класса.

Другой вариант - разрешить вызывающей стороне предоставить метод нашему алгоритму, который затем будет использоваться для выполнения фактического сравнения объектов. Переписать алгоритм таким образом для использования с настраиваемыми объектами довольно просто. Однако имейте в виду, что алгоритм нестабилен.

Начнем с класса Person

 class Person: 
 def __init__(self, name, age): 
 self.name = name 
 self.age = age 
 
 def __str__(self): 
 return self.name

Это довольно простой класс, у которого всего два свойства: name и age . Мы хотим использовать age качестве ключа сортировки, что мы сделаем, предоставив настраиваемую лямбда-функцию алгоритму сортировки.

Но сначала давайте посмотрим, как эта предоставленная функция используется в алгоритме. Вместо прямого сравнения с <= или >= мы вызываем функцию, чтобы определить, какой Person старше по возрасту:

 def partition(array, start, end, compare_func): 
 pivot = array[start] 
 low = start + 1 
 high = end 
 
 while True: 
 while low <= high and compare_func(array[high], pivot): 
 high = high - 1 
 
 while low <= high and not compare_func(array[low], pivot): 
 low = low + 1 
 
 if low <= high: 
 array[low], array[high] = array[high], array[low] 
 else: 
 break 
 
 array[start], array[high] = array[high], array[start] 
 
 return high 

 def quick_sort(array, start, end, compare_func): 
 if start >= end: 
 return 
 
 p = partition(array, start, end, compare_func) 
 quick_sort(array, start, p-1, compare_func) 
 quick_sort(array, p+1, end, compare_func)

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

 p1 = Person("Dave", 21) 
 p2 = Person("Jane", 58) 
 p3 = Person("Matthew", 43) 
 p4 = Person("Mike", 21) 
 p5 = Person("Tim", 10) 
 
 array = [p1,p2,p3,p4,p5] 
 
 quick_sort(array, 0, len(array) - 1, lambda x, y: x.age < y.age) 
 for person in array: 
 print(person)

Результат:

 Tim 
 Dave 
 Mike 
 Matthew 
 Jane

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

Оптимизация Quicksort

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

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

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

Популярным вариантом Quicksort является Multi-pivot Quicksort, который разбивает исходный массив на n меньших массивов, используя n-1 pivots. Однако в большинстве случаев используются только две точки поворота, не более.

Интересный факт: в реализации сортировки Java 7 использовалась быстрая сортировка с двумя поворотами, а также сортировка вставкой для меньших массивов.

Заключение

Как мы уже упоминали ранее, эффективность быстрой сортировки сильно зависит от выбора точки поворота - она может «повлиять» на сложность алгоритма во времени (и пространстве стека). Нестабильность алгоритма также может стать препятствием при использовании пользовательских объектов.

Однако, несмотря на все это, средняя временная сложность Quicksort, равная O (n * log ~n~ ), относительно низкое использование пространства и простая реализация, делают его очень эффективным и популярным алгоритмом.

Если вы хотите узнать больше, ознакомьтесь с другой нашей статьей « Алгоритмы сортировки в Python» , в которой рассматривается больше алгоритмов сортировки в Python, но не так подробно.