Автор оригинала: Gareth Dwyer.
В этом уроке мы рассмотрим алгоритм Quicksort с построчным объяснением. Мы рассмотрим, как работает алгоритм, построим его в ответ.это, а затем время, чтобы увидеть, насколько это эффективно.
Обзор и требования
Мы будем предполагать , что вы уже знаете, по крайней мере, что-то об алгоритмах сортировки и познакомились с идеей быстрой сортировки. К концу этого урока вы должны лучше понять, как это работает.
Мы также предположим, что вы рассмотрели некоторые более фундаментальные концепции информатики, особенно рекурсию , на которые опирается Quicksort.
Напомним, что Quicksort является одним из наиболее эффективных и наиболее часто используемых алгоритмов сортировки списка чисел. В отличие от своего конкурента, Mergesort, Quicksort может сортировать список на месте, без необходимости создавать копию списка и, следовательно, экономить требования к памяти.
Основная интуиция, лежащая в основе Quicksort, заключается в том, что если мы можем эффективно разделять список, то мы можем эффективно сортировать его. Разбиение списка на разделы означает, что мы выбираем элемент pivot в списке, а затем изменяем список, чтобы переместить все элементы, большие, чем pivot, вправо, а все меньшие элементы-влево.
После того, как сводная точка будет выполнена, мы можем выполнить ту же операцию с левой и правой частями списка рекурсивно, пока список не будет отсортирован.
Вот реализация Quicksort на Python. Прочтите его и посмотрите, имеет ли это смысл. Если нет, читайте ниже!
def partition(xs, start, end):
follower = leader = start
while leader < end:
if xs[leader] <= xs[end]:
xs[follower], xs[leader] = xs[leader], xs[follower]
follower += 1
leader += 1
xs[follower], xs[end] = xs[end], xs[follower]
return follower
def _quicksort(xs, start, end):
if start >= end:
return
p = partition(xs, start, end)
_quicksort(xs, start, p-1)
_quicksort(xs, p+1, end)
def quicksort(xs):
_quicksort(xs, 0, len(xs)-1)
Алгоритм разбиения
Идея, лежащая в основе алгоритма разбиения, кажется интуитивно понятной, но фактический алгоритм, позволяющий сделать это эффективно, довольно нелогичен.
Давайте начнем с самой простой части-с идеи. У нас есть список номеров, которые не отсортированы. Мы выбираем точку в этом списке и удостоверяемся, что все большие числа находятся справа от этой точки, а все меньшие числа-слева . Например, учитывая случайный список:
xs = [8, 4, 2, 2, 1, 7, 10, 5]
Мы могли бы выбрать последний элемент (5) в качестве точки поворота. Мы хотели бы, чтобы список (после разбиения на разделы) выглядел следующим образом:
xs = [4, 2, 2, 1, 5, 7, 10, 8]
Обратите внимание, что этот список не отсортирован, но у него есть некоторые интересные свойства. Наш поворотный элемент, 5 , находится в правильном месте (если мы полностью отсортируем список, этот элемент не будет перемещаться). Кроме того, все числа слева меньше, чем 5 и все числа справа больше.
Потому что 5 находится в правильном месте, мы можем игнорировать его после алгоритма разбиения (нам не нужно будет перемещать его снова). Это означает, что если мы сможем отсортировать два меньших подсписка слева и справа от 5 () [4, 2, 2, 1] и [7, 10, 8] ) затем весь список будет отсортирован. Каждый раз, когда мы можем эффективно разбить проблему на более мелкие подзадачи, мы должны думать о рекурсии как о инструменте для решения нашей основной проблемы. Используя рекурсию, нам часто даже не нужно думать о полном решении. Вместо этого мы определяем базовый случай (список длиной 0 или 1 всегда сортируется) и способ разделить большую проблему на меньшие (например, разбиение списка на две части), и почти по волшебству проблема решается сама собой!
Но мы немного забегаем вперед. Давайте посмотрим, как на самом деле реализовать алгоритм разбиения сам по себе, а затем мы можем вернуться к его использованию для реализации алгоритма сортировки.
Плохая реализация раздела
Вероятно, вы могли бы легко написать свой собственный алгоритм partition , который получает правильные результаты, не обращаясь к каким-либо реализациям учебников или не думая об этом слишком много. Например:
def bad_partition(xs):
smaller = []
larger = []
pivot = xs.pop()
for x in xs:
if x >= pivot:
larger.append(x)
else:
smaller.append(x)
return smaller + [pivot] + larger
В этой реализации мы создали два временных списка ( меньший и больший ). Затем мы берем элемент pivot в качестве последнего элемента списка ( pop берет последний элемент и удаляет его из исходного xs списка).
Затем мы рассмотрим каждый элемент x в списке xs . Те, которые меньше оси, мы храним в меньшем временном списке, а остальные переходят в больший временный список. Наконец, мы объединяем два списка с элементом pivot в середине, и мы разделили наш список.
Это гораздо легче прочитать, чем реализация в начале этого поста, так почему бы нам не сделать это так?
Основное преимущество Quicksort заключается в том, что он представляет собой алгоритм сортировки на месте . Хотя для примеров игрушек, которые мы рассматриваем, может показаться, что создание нескольких копий нашего списка не представляет большой проблемы, если вы пытаетесь отсортировать терабайты данных или если вы пытаетесь отсортировать любой объем данных на очень ограниченном компьютере (например, умные часы), то вы не хотите без необходимости копировать массивы.
В терминах информатики этот алгоритм имеет пространственную сложность O(2n) , где n – количество элементов в нашем массиве xs|/. Если мы рассмотрим наш пример выше xs = [8, 4, 2, 2, 1, 7, 10, 5] , нам нужно будет сохранить все 8 элементов в исходном массиве xs , а также три элемента ( [7, 10, 8] ] в большем массиве и четырех элементах ( [4, 2, 2, 1] ) в массиве меньшего размера|/. Это пустая трата места! С помощью некоторых хитрых трюков мы можем выполнить ряд операций подкачки исходного массива, и нам вообще не нужно делать никаких копий.
Обзор фактической реализации разделов
Давайте вытащим несколько ключевых частей хорошей функции partition , которые могут быть особенно запутанными, прежде чем переходить к подробному объяснению. Здесь это снова для справки.
def partition(xs, start, end):
follower = leader = start
while leader < end:
if xs[leader] <= xs[end]:
xs[follower], xs[leader] = xs[leader], xs[follower]
follower += 1
leader += 1
xs[follower], xs[end] = xs[end], xs[follower]
return follower
В нашей хорошей функции partition вы можете видеть, что мы выполняем некоторые операции подкачки (строки 5 и 8) на переданном xs , но мы никогда не выделяем новую память. Это означает , что хранилище остается постоянным до размера xs или O(n) в терминах информатики. То есть этот алгоритм имеет половину требования к пространству “плохой” реализации выше, и поэтому должен позволять нам сортировать списки, которые в два раза больше, используя тот же объем памяти.
Запутанная часть этой реализации заключается в том, что, хотя все основано на нашем элементе pivot (последний элемент списка в нашем случае), и хотя элемент pivot заканчивается где-то в середине списка в конце, мы фактически не касаемся элемента pivot до самого последнего свопа .
Вместо этого у нас есть два других счетчика ( follower и leader ), которые хитроумно перемещают меньшие и большие числа и неявно отслеживают, где должен находиться элемент pivot. Затем мы переключаем поворотный элемент в правильное место в конце цикла (строка 8).
лидер – это просто счетчик циклов. На каждой итерации он увеличивается на единицу, пока не дойдет до элемента pivot (конец списка). Последователь более тонкий, и он подсчитывает количество итераций подкачки, которые мы делаем, продвигаясь вверх по списку медленнее, чем лидер, отслеживая, где в конечном итоге должен оказаться наш элемент pivot.
Другая запутанная часть этого алгоритма находится в строке 4. Мы перемещаемся по списку слева направо. Все числа в настоящее время находятся слева от оси, но в конечном итоге мы хотим, чтобы “большие” элементы оказались справа .
Интуитивно вы ожидаете, что мы будем выполнять действие обмена, когда найдем элемент, который больше , чем ось, но на самом деле мы делаем обратное. Когда мы находим элементы, которые меньше , чем стержень, мы меняем местами лидера и последователя.
Вы можете думать об этом как о перемещении мелких предметов дальше влево. Поскольку лидер всегда опережает последователя, когда мы делаем своп, мы меняем небольшой элемент на другой, оставшийся в списке. Последователь смотрит только на “большие” предметы (те, которые лидер пропустил без каких-либо действий), поэтому, когда мы делаем обмен, мы меняем маленький предмет (лидер) на большой (последователь), что означает, что маленькие предметы будут двигаться влево, а большие-вправо.
Построчное обследование перегородки
Мы определяем partition с тремя аргументами, xs который является списком, который мы хотим отсортировать, start который является индексом первого рассматриваемого элемента и end который является индексом последнего рассматриваемого элемента.
Нам нужно определить аргументы start и end , потому что мы не всегда будем разбивать весь список на разделы. Позже, когда мы будем работать с алгоритмом сортировки, мы будем работать с все меньшими и меньшими подсписками, но поскольку мы не хотим создавать новые копии списка, мы будем определять эти подсписки, используя индексы к исходному списку.
В строке 2 мы начинаем с того, что оба наших указателя – последователь и лидер – совпадают с началом интересующего нас сегмента списка. Лидер будет двигаться быстрее, чем последователь, поэтому мы будем продолжать цикл до тех пор, пока лидер не упадет с конца сегмента списка ( while leader < end ).
Мы можем взять любой элемент, который мы хотим, в качестве элемента поворота, но для простоты мы просто выберем последний элемент. Затем в строке 4 мы сравниваем элемент leader с стержнем. Лидер собирается пройти через каждый элемент в нашем сегменте списка, поэтому это означает, что, когда мы закончим, мы сравним раздел с каждым элементом в списке.
Если элемент leader меньше или равен элементу pivot, нам нужно отправить его дальше влево и перенести больший элемент (отслеживаемый follower ) дальше вправо. Мы делаем это в строках 4-5, где, если мы находим случай, когда лидер меньше или равен развороту, мы меняем его местами с последователем . В этот момент последователь указывает на небольшой элемент (тот, который был лидером минуту назад), поэтому мы увеличиваем последователя на единицу, чтобы вместо этого отслеживать следующий элемент. Это имеет побочный эффект подсчета количества свопов, которые мы делаем, что, кстати, отслеживает точное место, где в конечном итоге должен оказаться наш элемент pivot.
Независимо от того, сделали мы своп или нет, мы хотим рассмотреть следующий элемент по отношению к нашему пивоту, поэтому в строке 7 мы увеличиваем лидер .
Как только мы выйдем из цикла (строка 8), нам нужно поменять элемент pivot (все еще находящийся в конце списка) на follower (который переместился вверх по одному для каждого элемента, который был меньше, чем pivot). Если это все еще сбивает с толку, посмотрите на наш пример еще раз:
xs = [8, 4, 2, 2, 1, 7, 10, 5]
В xs есть 4 элемента , которые меньше, чем стержень. Каждый раз, когда мы находим элемент, который меньше оси, мы увеличиваем follower на единицу. Это означает, что в
Последнее, что мы делаем, – это возвращаем индекс последователя, который теперь указывает на наш элемент pivot в его правильном месте. Нам нужно вернуть это, поскольку оно определяет две более мелкие подзадачи в нашем секционированном списке-теперь мы хотим отсортировать xs[0:4] (первые 4 элемента, которые образуют несортированный список) и xs[5:] (последние 3 элемента, которые образуют несортированный список).
xs = [4, 2, 2, 1, 5, 7, 10, 8]
Если вам нужен другой способ точно представить, как это работает, очень полезно просмотреть некоторые примеры вручную (то есть написать короткий случайно упорядоченный список ручкой и бумагой и выписывать новый список на каждом шаге алгоритма). Вы также можете посмотреть это подробное видео на YouTube , где KC и демонстрирует каждый шаг алгоритма с использованием бумажных стаканчиков менее чем за 5 минут!
Функция быстрой сортировки
Как только мы получим правильный алгоритм разбиения, сортировка станет легкой. Сначала мы определим вспомогательную функцию _quicksort для обработки рекурсии, а затем реализуем более красивую общедоступную функцию.
def _quicksort(xs, start, end):
if start >= end:
return
p = partition(xs, start, end)
_quicksort(xs, start, p-1)
_quicksort(xs, p+1, end)
Чтобы отсортировать список, мы разделяем его (строка 4), сортируем левый подсписок (строка 5: от начала исходного списка до точки поворота), а затем сортируем правый подсписок (строка 6: сразу после точки поворота до конца исходного списка). Мы делаем это рекурсивно, когда граница end перемещается влево , ближе к start , для левых подсписков , а граница start перемещается вправо, ближе к end , для правых подсписков. Когда начальная и конечная границы пересекаются (строка 2), мы закончили!
Первый вызов Quicksort всегда будет со всем списком, который мы хотим отсортировать, что означает, что 0 будет началом списка и len(xs)-1 будет концом списка. Мы не хотим, чтобы нам приходилось передавать эти дополнительные аргументы каждый раз, когда мы вызываем Quicksort из другой программы (например, в любом случае, когда она сама себя не вызывает), поэтому мы сделаем более красивую функцию-оболочку с этими значениями по умолчанию, чтобы запустить процесс.
def quicksort(xs):
return _quicksort(xs, 0, len(xs)-1)
Теперь мы, как пользователи функции сортировки, можем вызвать quicksort([4,5,6,2,3,9,10,2,1,5,3,100,23,42,1]) , передавая только список, который мы хотим отсортировать. Это, в свою очередь, вызовет функцию _quicksort , которая будет продолжать вызывать себя до тех пор, пока список не будет отсортирован.
Тестирование нашего алгоритма
Мы можем написать некоторый базовый код драйвера, чтобы взять наш недавно реализованный Quicksort для вращения. Создайте новый Python Repl и добавьте следующий код в main.py . Затем вставьте код, указанный в начале этого руководства, после импорта.
from datetime import datetime import random # create 100000 random numbers between 1 and 1000 xs = [random.randrange(1000) for _ in range(10)] # look at the first few and last few print(xs[:10]) #apply the algorithm quicksort(xs) # have a look at the results print(xs[:10])
Если вы запустите этот код, вы увидите отсортированный список. Это делает то, что мы ожидаем, но это не говорит нам о том, насколько эффективна быстрая сортировка, поэтому давайте рассмотрим ее поближе. Замените код в main.py со следующим, и снова добавьте код, указанный в начале этого руководства, после импорта в строке 3.
from datetime import datetime
import random
# create 100000 random numbers between 1 and 1000
xs = [random.randrange(1000) for _ in range(100000)]
# look at the first few and last few
print(xs[:10], xs[-10:])
# start the clock
t1 = datetime.now()
quicksort(xs)
t2 = datetime.now()
print("Sorted list of size {} in {}".format(len(xs), t2 - t1))
# have a look at the results
print(xs[:10], xs[-10:])
Код генерирует случайный список из 100 000 номеров и сортирует этот список примерно за 5 секунд. Вы можете сравнить производительность Quicksort с некоторыми другими распространенными алгоритмами сортировки, используя этот ответ .
Если вы хотите попробовать этот код, посетите мой ответ по адресу https://repl.it/@GarethDwyer1/quicksort . Вы сможете запустить код, увидеть результаты и даже развить его, чтобы продолжить разработку или тестирование самостоятельно.
Если вам нужна помощь, люди на сервере Repl discord очень дружелюбны и стремятся помочь людям учиться. Также не стесняйтесь оставлять комментарии ниже или следовать за мной в Twitter и задавать мне вопросы там.