Быстрая сортировка - это еще один алгоритм «разделяй и властвуй», подобный алгоритму merge_sort. Однако уникальный метод быстрой сортировки делает его на удивление эффективным и, следовательно, популярным.

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

Идея состоит в том, чтобы на каждом уровне подсписка захватить случайный элемент, также известный как точка поворота, и сравнить его с остальной частью списка, сдвигая меньшие значения влево, а большие. значения справа. Это случайно разместит наш сводный элемент в правильном индексе нашего списка! Выше вы можете видеть, что это сначала сделано с числом «4». Затем операция повторяется для подсписка слева с «1» в качестве точки поворота и «3» в качестве последней точки поворота.

Как только он достигает последнего элемента, все значения упорядочиваются, поэтому он просто восстанавливает себя, и готово! Левая сторона оси «4» в порядке.

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

Примечание: быстрая сортировка довольно эффективна при использовании произвольного поворотного селектора, так как он разделяет список на левую и правую части. Случайный выбор точки поворота гарантирует, что вы не сможете настроить ее для выполнения худшего сценария (который я сегодня объяснять не буду). Быстрая сортировка - это тот редкий алгоритм, в котором мы не описываем сценарий Big O как худший случай, а скорее как лучший вариант O (N * log N). Хорошо скользит сквозь щели. Это все.

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

def quicksort(list, start, end):
 if start >= end:
 return list

Как видите, наши параметры - это сам массив, начальный индекс (обычно 0), а конечный индекс - это длина массива минус 1 (поскольку компьютеры считают от 0).

Теперь давайте построим логику выбора случайного индекса в списке. К счастью, у python есть случайный модуль, который я могу импортировать, чтобы позаботиться об этой логике за меня (randrange). Вот как это будет выглядеть:

pivot_idx = randrange(start, end)
pivot_element = list[pivot_idx]

Итак, пока я сортирую элементы слева или справа от сводного индекса, где мне хранить этот сводный индекс?

Поместим его в конец массива. Таким образом, я сортирую остальную часть массива на этом уровне подсписка. Как только я закончу сортировку, мне будет намного проще вернуть его на место. Это работает… поверьте мне. Если я заблудился, посмотрите моего человека Кей Си Энга и его объяснение. Обратите внимание, что он удобно расположен в конце массива с самого начала.

Итак, позвольте мне заменить случайный индекс последним индексом:

list[end], list[pivot_idx] = list[pivot_idx], list[end]

Теперь нам нужны наши указатели. Это объекты, которые будут отслеживать нашу логику для сортировки левого и правого подсписок (также называемых разделами).

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

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

Вот как это будет выглядеть:

Посмотрите, как lesser_than_pointer начинается с начала (start), а цикл for выполняет итерацию по массиву. Как только он обнаруживает, что индекс меньше list [end], он выполняет обмен и увеличивает позицию индекса lesser_than_pointer на 1.

Как только это будет сделано - вне цикла for, мы захотим переместить точку поворота с конца массива в текущую позицию индекса lesser_than_pointer, которому она принадлежит.

list[end], list[lesser_than_pointer] = list[lesser_than_pointer], list[end]

Итак, это вся операция на одном уровне подсписка. Чтобы в конечном итоге выполнить базовый вариант, я хочу увеличить индекс start на 1, чтобы в какой-то момент рекурсия прекратилась.

Это вся операция для одного уровня подсписка. Чтобы сделать его рекурсивным, я просто вызываю функцию внутри функции, и все готово!

Вывод

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