Быстрая сортировка очень похожа на сортировку слиянием в том смысле, что этот алгоритм помогает программистам разделять и властвовать. Он выбирает элементы в качестве стержня, после чего создает разделы в массиве. Quick sort имеет множество версий, и каждая из них выбирает стержень по-разному.
Команда partition() является, пожалуй, самой важной частью быстрой сортировки. Цели раздела получают массив вместе с элементом массива x в качестве стержня. Вы должны поместить x в нужную позицию, то есть в отсортированный массив, после чего перед ним будут размещены элементы, которые меньше x. Наконец, после него нужно поместить элементы, которые больше x. Убедитесь, что вы выполняете все это за линейное время.
Стоит также помнить, что quick sort создает разделы в массивах, после чего дважды вызывает себя для сортировки получившихся в результате подмассивов. Подобный алгоритм невероятно удобен при работе с большими массивами данных. Это связано с тем, что O(n2) – его наихудшая сложность. Два начальных члена используются для рекурсивных вызовов, а последний член пригодится в процессе разбиения. Элементы, меньшие, чем стержень, обозначаются k.
Количество времени, которое обычно занимает быстрая сортировка, зависит от стратегии разбиения, а также от входного массива.
Три случая быстрой сортировки
Как и различные другие алгоритмы сортировки, быстрая сортировка также имеет свои сценарии. Давайте обсудим их ниже:
Наихудший случай
Этот тип случая имеет место всякий раз, когда процесс разбиения выбирает наименьший или наибольший элемент в качестве стержня. Учитывая рассмотренную ранее стратегию разбиения, при которой в качестве стержня каждый раз выбирается последний элемент, сценарий наихудшего места будет иметь место, когда массив будет отсортирован в порядке убывания или возрастания. Рекуррентное соотношение для наихудшего случая выглядит следующим образом:
T(n) = T(0) + T(n-1) + (n)что эквивалентно T(n) = T(n-1) + (n).
Наилучший случай
Наилучший случай имеет место всякий раз, когда процесс разбиения выбирает средний элемент в качестве стержня. Рекуррентное соотношение для лучшего случая выглядит следующим образом:
T(n) = 2T(n/2) + (n)
Средний случай
Необходимо рассмотреть каждую перестановку массива и вычислить время, необходимое каждой перестановке для выполнения анализа случая. Конечно, этот процесс может быть довольно сложным даже для опытных программистов. Тем не менее, принимая во внимание случай, когда в разделе размещается O(n/9) наряду с O(9n/10) элементами, можно получить оценку среднего случая. Рекуррентность этого случая выглядит следующим образом.
T(n) = T(n/9) + T(9n/10) + (n)
Общие вопросы, задаваемые о быстрой сортировке
Хотя существует множество вопросов, задаваемых о быстрой сортировке, приведенные ниже являются, пожалуй, самыми распространенными:
Является ли quick sort стабильным алгоритмом?
Реализация quick sort по умолчанию не обладает стабильностью. Тем не менее, можно добавить стабильности алгоритмам сортировки, рассматривая индекс как параметр для сравнения.
Что такое трехсторонняя быстрая сортировка?
Когда речь идет об обычном алгоритме быстрой сортировки, мы выбираем элемент в качестве стержня, создаем раздел в массиве. После этого мы повторяем сортировку для подмассивов, находящихся справа и слева от стержня.
Является ли Quick Sort алгоритмом in-place?
Согласно широкому определению алгоритма in-place, быстрая сортировка действительно относится к этому типу алгоритмов сортировки. Это связано с тем, что он использует дополнительное пространство для хранения вызовов рекурсивных функций. Однако он никак не манипулирует входными данными.
Быстрее, чем большинство алгоритмов сортировки
Хотя нельзя отрицать, что временная сложность quick sort в худшем случае составляет O(n2), по сравнению с heap sort, merge sort и множеством других алгоритмов сортировки, quick sort работает невероятно быстро. Одной из причин этого является то, что вы можете эффективно реализовать его внутренний цикл в нескольких типах данных и архитектур реального мира.
Более того, вы можете реализовать быструю сортировку различными способами, просто изменив выбор поворотной точки. Это минимизирует возникновение наихудшего случая для любого типа данных. Тем не менее, программисты обычно предпочитают использовать сортировку слиянием, когда данных слишком много, особенно если они находятся во внешнем хранилище.
Что насчет использования быстрой сортировки в связанных списках
Когда речь заходит о связанных списках, все происходит совсем по-другому из-за различий в распределении памяти массива. Узлы связанных списков сильно отличаются от массивов и часто не являются соседними в памяти. Более того, связанные списки позволяют вводить элементы в центре, что невозможно в массиве. В таких сценариях программисты предпочитают использовать сортировку слиянием, поскольку она оказывается более жизнеспособным вариантом по сравнению с быстрой сортировкой.
Почему программисты предпочитают быструю сортировку сортировке массивов
По своей сути, быстрая сортировка является простой сортировкой на месте, что означает, что она не нуждается в дополнительном хранилище. С другой стороны, сортировка слиянием требует O(N) дополнительного хранилища. Для тех, кому интересно, N означает размер массива, который может быть невероятно большим. Деаллокация и выделение дополнительного пространства, необходимого для сортировки слиянием, увеличивает время работы алгоритма.
Сравнивая среднюю сложность, легко заметить, что средняя сложность обоих типов сортировки равна O(NlogN). Однако их константы, как правило, отличаются. Когда речь идет о массивах, сортировка слиянием не удается, поскольку она использует дополнительное пространство хранения O(N). Наиболее практичные реализации быстрой сортировки используют рандомизированную версию. Средняя временная сложность этой версии составляет O(nLogn). Стоит также помнить, что существует возможность худшего случая с рандомизированной версией. Однако она не проявляется для специфических шаблонов, таких как отсортированный массив.
Алгоритм быстрой сортировки довольно дружелюбен к кэшу благодаря отличной локальности ссылок, особенно если использовать его для массивов. Более того, quick sort также является хвостовой рекурсией, что означает необходимость оптимизации хвостовых вызовов.