Qsort быстрая сортировка таблицы

Содержание

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

Быстрая сортировка представляет собой усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал его быстрой сортировкой.

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

Тем самым массив разбивается на две части:

  • не отсортированные элементы слева от разрешающего элемента;
  • не отсортированные элементы справа от разрешающего элемента.

Чтобы отсортировать эти два меньших подмассива, алгоритм рекурсивно вызывает сам себя.

Если требуется сортировать больше одного элемента, то нужно

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

Ключевым элементом быстрой сортировки является алгоритм переупорядочения .

Рассмотрим сортировку на примере массива:

10, 4, 2, 14, 67, 2, 11, 33, 1, 15.

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

Пусть крайний левый элемент — разрешающий pivot . Установим указатель left на следующий за ним элемент; right — на последний. Алгоритм должен определить правильное положение элемента 10 и по ходу дела поменять местами неправильно расположенные элементы.

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

Указатель left перемещается до тех пор, пока не покажет элемент больше 10; right движется, пока не покажет элемент меньше 10.

Эти элементы меняются местами и движение указателей возобновляется.

Процесс продолжается до тех пор, пока right не окажется слева от left .

Тем самым будет определено правильное место разрешающего элемента.

Осуществляется перестановка разрешающего элемента с элементом, на который указывает right .

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

Реализация алгоритма быстрой сортировки на Си

Qsort быстрая сортировка таблицы

«Быстрая сортировка», хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод основан на подходе «разделяй-и-властвуй». Общая схема такова:

  1. из массива выбирается некоторый опорный элемент a[i],
  2. запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] — вправо,
  3. теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого,
  4. для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

В конце получится полностью отсортированная последовательность.

Рассмотрим алгоритм подробнее.


Разделение массива

На входе массив a[0]. a[N] и опорный элемент p, по которому будет производиться разделение.

  1. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.
  2. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j]
    Общий алгоритм Псевдокод.
    Реализация на Си.

Каждое разделение требует, очевидно, Theta(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Однако, возможен случай таких входных данных, на которых алгоритм будет работать за O(n 2 ) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге. Вообще говоря, малореальная ситуация.

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

Сортировка использует дополнительную память, так как приблизительная глубина рекурсии составляет O(log n), а данные о рекурсивных подвызовах каждый раз добавляются в стек.

Модификации кода и метода

Из-за рекурсии и других «накладных расходов» Quicksort может оказаться не столь уж быстрой для коротких массивов. Поэтому, если в массиве меньше CUTOFF элементов (константа зависит от реализации, обычно равна от 3 до 40), вызывается сортировка вставками. Увеличение скорости может составлять до 15%.

Для проведения метода в жизнь можно модифицировать функцию quickSortR, заменив последние 2 строки на

Таким образом, массивы из CUTOFF элементов и меньше досортировываться не будут, и в конце работы quickSortR() массив разделится на последовательные части из -50 , так что интерес скорее теоретический, нежели практический. Однако, поведение «быстрой сортировки» является «эталоном» для аналогично реализованных алгоритмов типа «разделяй-и-властвуй». Не везде можно свести вероятность худшего случая практически к нулю, поэтому такая ситуация заслуживает изучения.

Пусть, для определенности, каждый раз выбирается наименьший элемент amin . Тогда процедура разделения переместит этот элемент в начало массива и на следующий уровень рекурсии отправятся две части: одна из единственного элемента amin, другая содержит остальные n-1 элемента массива. Затем процесс повторится для части из (n-1) элементов.. И так далее..
При использовании рекурсивного кода, подобного написанному выше, это будет означать n вложенных рекурсивных вызовов функции quickSort.
Каждый рекурсивный вызов означает сохранение информации о текущем положении дел. Таким образом, сортировка требует O(n) дополнительной памяти.. И не где-нибудь, а в стеке. При достаточно большом n такое требование может привести к непредсказуемым последствиям.

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

Псевдокод.
Реализация на Си.

Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

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

Быстрая сортировка (англ. quick sort, сортировка Хоара) — один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы [math]O(n\log)[/math] , что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из [math]n[/math] элементов в худшем случае может составить [math]\Theta(n^2)[/math] , на практике этот алгоритм является одним из самых быстрых.

Содержание

Алгоритм [ править ]

Быстрый метод сортировки функционирует по принципу «разделяй и властвуй».

  • Массив [math] a[l \ldots r][/math] типа [math] T [/math] разбивается на два (возможно пустых) подмассива [math] a[l \ldots q][/math] и [math] a[q+1 \ldots r][/math] , таких, что каждый элемент [math] a[l \ldots q][/math] меньше или равен [math] a[q][/math] , который в свою очередь, не превышает любой элемент подмассива [math] a[q+1 \ldots r][/math] . Индекс вычисляется в ходе процедуры разбиения.
  • Подмассивы [math] a[l \ldots q][/math] и [math] a[q+1 \ldots r][/math] сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
  • Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив [math] a[l \ldots r][/math] оказывается отсортированным.

Псевдокод [ править ]

Для сортировки всего массива необходимо выполнить процедуру [math]\mathrm[/math] .

Разбиение массива [ править ]

Основной шаг алгоритма сортировки — процедура [math]\mathrm[/math] , которая переставляет элементы массива [math]a[l \ldots r][/math] типа [math] T [/math] нужным образом. Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент [math] a[(l + r) / 2] [/math] . Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.

Переменная [math] v [/math] сохраняет значение разделяющего элемента [math] a[(l + r) / 2] [/math] , a [math] i [/math] и [math] j [/math] представляет собой, соответственно, указатели левого и правого просмотра. Цикл разделения увеличивает значение [math] i [/math] и уменьшает значение [math] j [/math] на [math] 1 [/math] , причем условие, что ни один элемент слева от [math] i [/math] не больше [math] v [/math] и ни один элемент справа от [math] j [/math] не меньше [math] v [/math] , не нарушается. Как только значения указателей пересекаются, процедура разбиения завершается.

Асимптотика [ править ]

Худшее время работы [ править ]

Предположим, что мы разбиваем массив так, что одна часть содержит [math]n — 1[/math] элементов, а вторая — [math]1[/math] . Поскольку процедура разбиения занимает время [math]\Theta(n)[/math] , для времени работы [math]T(n)[/math] получаем соотношение:

[math]T(n) = T(n — 1) + \Theta(n) = \sum\limits_^ \Theta(k) = \Theta(\sum\limits_^ k) = \Theta(n^2)[/math] .

Мы видим, что при максимально несбалансированном разбиении время работы составляет [math]\Theta(n^2)[/math] . В частности, это происходит, если массив изначально отсортирован.

Способ построить массив с максимальным количеством сравнений при выборе среднего элемента в качестве опорного [ править ]

В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает [math]\Theta(n^2)[/math] сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться [math]1[/math] , а в другом [math] n — 1 [/math] элемент).

Заполним сначала массив [math]a[/math] длины [math]n[/math] элементами от [math]1[/math] до [math] n [/math] , затем применим следующий алгоритм (нумерация с нуля):

Тогда на каждом шаге в качестве среднего элемента будет ставиться самый крупный элемент.

При выполнении [math]\mathrm[/math] делается [math]\Theta(n)[/math] сравнений из-за того, что с помощью индексов [math]i[/math] и [math]j[/math] мы проходим в лучшем случае [math]\Omega(n)[/math] элементов (если функция прекращает свою работу, как только индексы встречаются), в худшем случае [math]O(2n)[/math] элементов (если оба индекса полностью проходят массив). При каждом изменении индекса делается сравнение, значит, процедура [math]\mathrm[/math] делает [math]\Theta(n)[/math] сравнений с точностью до константы.

Рассмотрим, какой элемент будет выбираться опорным на каждом шаге. [math]\mathrm[/math] на каждом шаге меняет местами последний и центральный элементы, поэтому в центре оказывается самый крупный элемент. А [math]\mathrm[/math] делает абсолютно симметричные этой процедуре операции, но в другую сторону: меняет местами центральный элемент с последним, так что самый крупный элемент становится последним, а затем выполняет на массиве длины на один меньшей ту же операцию. Получается, что опорным всегда будет выбираться самый крупный элемент, так как [math] \mathrm [/math] на массиве любой длины будет выполнять операции, обратные [math]\mathrm[/math] . Фактически, [math]\mathrm[/math] — это [math]\mathrm[/math] , запущенная в другую сторону. Также стоит отметить, что процедура разбиения будет делать на каждом шаге только одну смену элементов местами. Сначала [math]i[/math] дойдет до середины массива, до опорного элемента, [math]j[/math] останется равным индексу последнего элемента. Затем произойдет [math]\mathrm[/math] и [math]i[/math] снова начнет увеличиваться, пока не дойдет до последнего элемента, [math]j[/math] опять не изменит свою позицию. Потом произойдет выход из [math]\mathrm[/math] .

Разбиение массива будет произведено [math]\Theta(n)[/math] раз, потому что разбиение производится на массивы длины [math]1[/math] и [math] n — 1 [/math] из-за того, что на каждом шаге разбиения в качестве опорного будет выбираться самый крупный элемент (оценка на худшее время работы доказана выше). Следовательно, на массиве, который строится описанным выше способом, выполняется [math]\Theta(n)[/math] [math]\mathrm[/math] и [math]\Theta(n)[/math] сравнений для каждого выполнения [math]\mathrm[/math] . Тогда быстрая сортировка выполнит [math]\Theta(n^2)[/math] сравнений для массива, построенного таким способом.

Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента [ править ]

Рассмотрим алгоритм построения массива, на котором быстрая сортировка с детерминированным выбором опорного элемента будет делать максимальное (в данном случае — [math]\Theta(n^2)[/math] ) количество сравнений. Такое число сравнений достигается при разбиении на массивы длиной [math]1[/math] и [math]n-1[/math] на каждой итерации. Создадим массив [math]a[/math] длины [math]n[/math] , заполненный элементами типа [math]pair[/math] . Такой элемент хранит пару значений [math](val, key)[/math] , где [math]val[/math] — элемент массива, а [math]key[/math] — индекс. Изначально [math]a[i][/math] элемент имеет вид [math](0, i)[/math] .

Далее, запустим для данного массива алгоритм быстрой сортировки. Сравниваем два элемента типа [math]pair[/math] по их значениям [math]val[/math] . На каждом шаге будем выполнять следующие действия: при обращении к [math]i[/math] -ому элементу в качестве опорного на шаге под номером [math]k[/math] , присвоим [math]val = n-k+1[/math] для элемента [math]a[i][/math] . Затем выполним шаг сортировки. После завершения работы алгоритма быстрой сортировки, дополнительно отсортируем получившиеся элементы [math]pair[/math] по значениям [math]key[/math] . Искомым будет являться массив элементов [math]val[/math] в соответствующей последовательности.

Пример для [math]n = 4[/math] , при последовательном выборе опорных элементов [math]2, 2, 1, 1[/math] .

Покажем, почему на данном массиве будет достигаться максимальное время работы быстрой сортировки. На этапе построения мы каждый раз присваивали опорному элементу максимальное значение. Следовательно, при выполнении [math]\mathrm[/math] алгоритм в качестве опорного всегда будет выбирать наибольший элемент массива (выборка будет производится в том же порядке ввиду детерминированности определения опорного элемента). Таким образом, так как каждый раз массив разбивается на две части — большие или равные опорному элементы и меньшие его — на каждом шаге имеем разбиение на массивы длины [math]1[/math] и [math]n-1[/math] , чего мы, собственно, и добивались. При таком выполнении алгоритма происходит [math]\Theta(n^2)[/math] разделений на два подмассива, и на каждом разделении выполняется [math]\Theta(n^2)[/math] сравнений. Следовательно, на данном массиве быстрая сортировка работает за [math]\Theta(n^2)[/math] .

Среднее время работы [ править ]

Построение массива
Шаг 1.0 Шаг 1.1 Шаг 1.2 Шаг 2.0 Шаг 2.1 Шаг 2.2 Шаг 3.0
1 2 3 4
0 0 0
1 2 3 4
0 4 0 0
1 4 3 2
0 0 0 4
1 4 3 2
0 0 4
1 4 3 2
0 3 0 4
1 3 4 2
0 0 3 4
1 3 4 2
0 3 4
Шаг 3.1 Шаг 3.2 Шаг 4.0 Шаг 4.1 Шаг 4.2 Результат
1 3 4 2
2 0 3 4
3 1 4 2
0 2 3 4
3 1 4 2
2 3 4
3 1 4 2
1 2 3 4
3 1 4 2
1 2 3 4
1 2 3 4
2 4 1 3
Итоговый массив

Пусть [math]X[/math] — полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений. Переименуем элементы массива как [math]z_1 \ldots z_n[/math] , где [math]z_i[/math] наименьший по порядку элемент. Также введем множество [math]Z_ = \ \ldots z_j\>[/math] .

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

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

[math]X = \sum\limits_^\sum\limits_^ X_[/math] , где [math]X_ = 1[/math] если произошло сравнение [math]z_i[/math] и [math]z_j[/math] и [math]X_ = 0[/math] , если сравнения не произошло.

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

Осталось вычислить величину [math]Pr\[/math] — вероятность того, что [math]z_i[/math] сравнивается с [math]z_j[/math] . Поскольку предполагается, что все элементы в массиве различны, то при выборе [math]x[/math] в качестве опорного элемента впоследствии не будут сравниваться никакие [math]z_i[/math] и [math]z_j[/math] для которых [math]z_i \lt x \lt z_j[/math] . С другой стороны, если [math]z_i[/math] выбран в качестве опорного, то он будет сравниваться с каждым элементом [math]Z_[/math] кроме себя самого. Таким образом элементы [math]z_i[/math] и [math]z_j[/math] сравниваются тогда и только тогда когда первым в множестве [math]Z_[/math] опорным элементом был выбран один из них.

[math] E[X] = \sum\limits_^\sum\limits_^ \dfrac <2> = \sum\limits_^\sum\limits_^ \dfrac 2 \lt \sum\limits_^\sum\limits_^ \dfrac 2 [/math] [math]= \sum\limits_^O(\log n) = O(n \log n) [/math]

Лемма:
Время работы алгоритма быстрой сортировки равно [math]O(n \log n)[/math] .
Доказательство:
[math]\triangleright[/math]
[math]\triangleleft[/math]

Mатожидание времени работы быстрой сортировки будет [math]O(n \log n)[/math] .

Модификации [ править ]

Нерекурсивная реализация быстрой сортировки [ править ]

Для выполнения быстрой сортировки можно воспользоваться стеком, в котором в виде сортируемых подмассивов содержится перечень действий, которые предстоит выполнить. Каждый раз когда возникает необходимость в обработке подмассива, он выталкивается из стека. После разделения массива получаются два подмассива, требующих дальнейшей обработки, которые и заталкиваются в стек. Представленная ниже нерекурсивная реализация использует стек, заменяя рекурсивные вызовы помещением в стек параметров функции, а вызовы процедур и выходы из них — циклом, который осуществляет выборку параметров из стека и их обработку, пока стек не пуст. Мы помещаем больший из двух подмассивов в стек первым с тем, чтобы максимальная глубина стека при сортировке [math]N[/math] элементов не превосходила величины [math]\log n[/math] .

В качестве альтернативного варианта можно использовать обычную рекурсивную версию, в которой вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит [math]\log n[/math] , а в худшем случае вырожденного разделения она вообще будет не более [math]1[/math] — вся обработка пройдёт в цикле первого уровня рекурсии.

Улучшенная быстрая сортировка [ править ]

Выбор медианы из первого, среднего и последнего элементов в качестве разделяющего элемента и отсечение рекурсии меньших подмассивов может привести к существенному повышению эффективности быстрой сортировки. Функция [math]\mathrm[/math] возвращает индекс элемента, являющегося медианой трех элементов. После этого он и средний элемент массива меняются местами, при этом медиана становится разделяющим элементом. Массивы небольшого размера (длиной [math] M = 11[/math] и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется сортировка вставками.

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

Быстрая сортировка с разделением на три части [ править ]

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

В основу программы положено разделение массива на три части: на элементы,меньшие разделяющего элемента [math] a[l] \ldots a[i][/math] , элементы, равные разделяющему элементу [math]a[i+1] \ldots a[j-1][/math] , и элементы большие разделяющего элемента [math]a[j] \ldots a[r][/math] . После этого сортировка завершается двумя рекурсивными вызовами.

Элементы массива равные разделяющему элементу находятся между [math] l [/math] и [math] p [/math] и между [math] q [/math] и [math] r [/math] . В разделяющем цикле, когда указатели просмотра перестают изменяться и выполняется обмен значениями [math] i [/math] и [math] j [/math] , каждый из этих элементов проверяется на предмет равенства разделяющему элементу. Если элемент, который сейчас находится слева, равен разделяющему элементу, то при помощи операции обмена он помещается в левую часть массива, если элемент, который сейчас находится справа, равен разделяющему элементу, то в результате операции обмена он помещается в правую часть массива. После того как указатели пересекутся, элементы, равные разделяющему элементу и находящиеся на разных концах массива, после операции обмена попадают в свои окончательные позиции. После этого указанные ключи могут быть исключены из подмассивов, для которых выполняются последующие рекурсивные вызовы.

Параллельная сортировка [ править ]

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

Introsort [ править ]

Для предотвращения ухудшения времени работы быстрой сортировки до [math]O(n^2)[/math] при неудачных входных данных, также можно использовать алгоритм сортировки Introsort. Он использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Так как после нескольких итераций быстрой сортировки с применением разных эвристик массив с большей вероятностью окажется «почти отсортированным», то пирамидальная сортировка может довольно быстро закончить дело. Также, пирамидальная сортировка хороша тем, что требует [math]O(1)[/math] дополнительной памяти, в отличие от, например, сортировки слиянием, где потребуется [math]O(n)[/math] дополнительной памяти.

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

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

А лгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за n·log(n) шагов. В худшем случае сложность опускается до порядка n 2 , хотя такая ситуация довольно редкая. Быстрая сортировка обычно быстрее других «скоростных» сортировок со сложностью порядка n·log(n). Быстрая сортировка не устойчивая. Обычно, она преподносится как рекурсивная, однако, может быть с помощью стека (возможно, и без него, не проверено) сведена к итеративной, при этом потребуется не более n·log(n) дополнительной памяти.

Начнём с задачи, которую обычно называют Bolts & Nuts (Болты и Гайки). Вы пошли в магазин и купили болтов и гаек, много, целых два ведра. В одном ведре болты, в другом гайки. При этом известно, что для каждого болта из ведра есть соответствующая ему по размеру гайка, и для каждой гайки есть соответствующий по размеру болт. Одна беда — у вас отключили свет и вы не можете сравнить болт с болтом и гайку с гайкой. Вы можете сравнить только гайку с болтом и болт гайкой и проверить, подходят они друг другу или нет. Задача — найти для каждой гайки соответствующий ей болт.

Пусть у нас n пар болт-гайка. Самое простое решение — «в лоб» — берём гайку и находим для неё болт. Всего надо будет проверить n болтов. Поле этого берём вторую гайку, находим для неё болт, предстоит сделать уже n-1 проверку. И так далее. Всего надо будет сделать n + (n-1) + (n-2) + . + 1 = n 2 /2 шагов. Существует ли более простое решение?

Самое быстрое (из известных мне) решение не самое очевидное. Применим подход «разделяй и властвуй». Если множество, которое мы хотим обработать слишком большое, то разобьём его на более мелкие и применим рекурсивно наш алгоритм к каждому из них. В конце концов, когда данных будет немного, обработаем и обратно соберём их вместе.

Возьмём любой (случайный) болт и с его помощью разобьём все гайки на те, которые меньше, и те которые больше, чем нужно для этого болта. Конечно, во время разбиения мы найдём и соответствующую ему гайку. Таким образом мы получим две кучи гаек — те, которые больше и те, которые меньше. С помощью найденной гайки разобьём все болты на те, которые меньше, и те, которые больше, чем первоначальный болт. Получим две кучи болтов, мелкие и крупные.

Далее, из кучи мелких болтов выберем случайный болт и с его помощью разобьём кучу гаек (тех, которые мелкие) на две кучи. Во время разбиения найдём подходящую гайку, с помощью которой разобьём мелкие болты на две кучи и т.д. То же самое проделаем и с большей кучей. Рекурсивно будем применять этот алгоритм к каждой «подкуче». Таким образом, предстоит сделать порядка n·log(n) шагов.

Алгоритм быстрой сортировки напоминает решение нашей задачи. Сначала мы находим опорный элемент — это случайный элемент из множества, относительно которого мы будем проводить разбиение. Далее разобьём множество на три — элементы, которые больше опорного, равны ему и элементы, которые меньше. После чего рекурсивно применим алгоритм к двум оставшимся подмножествам (меньше и больше), если их длина больше единицы.

Рекурсивное решение

Ф ункция принимает в качестве аргументов массив и левую и правую границу массива. В самом начале левая граница это 0, а правая — длина массива минус один. Нам понадобятся следующие переменные

указывают на левый и правый элементы,

первая переменная для обмена при сортировке, вторая будет хранить значение опорного элемента. Сначала задаём начальные значения

Здесь следует сразу же оговориться. Выбирать всегда средний элемент в качестве опорного – достаточно рискованно. Если известно, какой элемент будет выбран в качестве опорного, то можно подобрать такую последовательность, для которой сортировка будет происходить максимально медленно, за время порядка n 2 . Поэтому в качестве элемента, относительно которого будет сортировка, берут либо случайный элемент, либо медиану из первого, последнего и среднего элементов.

Пока i будет меньше j (пока они не пересекутся) делаем следующее. Во первых, нужно пропустить все уже отсортированные элементы

Далее, если границы ещё не пересеклись, то в случае, если порядок нарушен, то следует обменять местами переменные, после чего опять инкрементировать i и декрементировать j, чтобы не зациклиться.

Здесь, однако, возможна ошибка. i вряд ли переполнится — размер массива не больше, чем максимальное значение типа size_t, умноженное на размер элемента массива байт (более сложные варианты даже рассматривать не будем). Но вот переменная j вообще-то может перейти через нуль. Так как переменная целочисленная, то при переходе через нуль её значение станет больше, чем i, что приведёт к зацикливанию. Поэтому необходима превентивная проверка.

После этого цикла i и j пересекутся, i станет больше j и мы получим ещё два массива, для которых следует применить сортировку: массив от левой границы до i, и массив от j до правой границы, если, конечно, мы не вышли за пределы границ.

Функция называется qsortx, чтобы не спутать со стандартной функцией быстрой сортировки qsort.

Итеративное решение

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

Какая самая быстрая quicksort — таблица лиги для сортировки алгоритмов?

Я пытался оптимизировать свою быстродействующую сортировку для производительности. Для 4M (1

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

Что касается вашего другого вопроса — как оптимизировать вашу быструю сортировку — не видя своего кода, трудно сказать наверняка. Вот список общих оптимизаций быстрой сортировки, которые вы можете попробовать.

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

Добавление интроспекции. Introsort — это быстрый вариант quicksort, который отслеживает глубину рекурсии и переключается на heapsort, когда похоже, что алгоритм дегенерирует. Это гарантирует, что время выполнения будет O (n log n) и берет только небольшую стоимость, если этот случай не запускается.

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

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

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

Макс Петров июнь 2013

Алгоритм предложен Чарльзом Хоаром в 1960 году. Эффективность O(n log n) обменов при сортировке n элементов.

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

Известным недостатком алгоритма является его рекурсивность, которая вызывает необходимость расходования памяти компьютера на запись адресов возврата из процедур сортировки каждого из подмассивов. Зависимость величины дополнительной памяти от числа элементов в исходном массиве характеризуется величиной n — 1.

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

Таблица. Время работы быстрой сортировки и сортировки расческой
для периодических массивов одноразрядных десятичных чисел (9, 6, 3, 8, 5, 2, 7, 4, 1, 0. )

Qsort быстрая сортировка таблицы

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

O(n 2 ). В тоже время такой алгоритм как сортировка вставкой — с такими случаями справляется «на ура», сортируя со скоростью

O(n). Поэтому используем здесь следующий подход: если в сортируемой последовательности в алгоритме быстрой сортировке остается меньше cutoff элементов — они сортируется сортировкой вставками. cutoff — некоторая константа(которая зависит от начальных условий и обычно равна 3-40).

Подробно:

По книге Джона Бентли:
«Жемчужины программирования»

«. Функция qsort1 быстро сортирует массив случайных чисел, но что, если на вход будет подана уже упорядоченная последовательность? Программисты часто используют сортировку для того, чтобы одинаковые элементы оказались рядом. Следовательно, нужно рассмотреть крайний случай: массив из n одинаковых элементов. Сортировка вставкой работает на таких данных очень быстро: каждый элемент сдвигается на 0 позиций, поэтому время выполнения растет как О(n). Функция qsort1 справляется с такими данными очень плохо. Каждое из n-1 разбиений требует время О(n) для выделения одного элемента, поэтому полное время выполнения растет как О(n 2 ). Время обработки для n = 1 000 000 возрастает с одной секунды до двух часов.

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

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

Но как такой код будет работать в ситуации, когда все элементы равны? Первая мысль: пропустить эти элементы, чтобы не делать лишней работы, но в результате получается квадратичный для массива из одинаковых элементов алгоритм. Поэтому каждое сканирование будет останавливаться на одинаковых элементах, которые затем будут обмениваться. Хотя в этом варианте обменов будет производиться больше, чем требуется, такая программа будет превращать худший случай с массивом из одинаковых элементов в лучший, требующий почти в точности n*log2n и сравнений. Псевдокод, реализующий описанный алгоритм разбиения, примет вид:

Избавляясь от квадратичного поведения в худшем случае, этот код и в среднем делает меньше обменов, чем qsort1.

Рассмотренные нами программы быстрой сортировки разбивали массив относительно первого встреченного элемента. Это хорошо подходит для случайных входных данных, но может сильно замедлить работу для некоторых упорядоченных последовательностей. Если массив уже отсортирован по возрастанию, его придется разбивать относительно первого элемента, затем относительно второго и так далее, что потребует времени О(n 2 ). Мы можем избежать этого, выбирая элемент для разбиения случайным образом — обменивая местами элемент х[l] со случайным элементом из диапазона x[l..u]:

swap(l, randint(l, u))

Если у вас нет функции randint, обратитесь к задаче, которая посвящена написанию собственного генератора случайных чисел(прим. ред.:на данном сайте этому посвящана задача собственный генератор случайных чисел). Каким бы кодом вы ни пользовались, внимательно проследите за тем, чтобы функция randint возвращала значение из диапазона [l, u] — выход за его границы приведет к ошибкам. Объединив случайный выбор центрального элемента с двусторонним разбиением, мы получим программу быстрой сортировки, работающую за время O(n*log n) для любого входного массива. Усреднение делается вызовом генератора случайных чисел, а не анализом возможного распределения входных данных.

Наша программа быстрой сортировки большую часть времени тратит на сортировку очень маленьких подмножеств. Такие массивы было бы проще всего сортировать каким-либо несложным методом вроде сортировки вставкой, а не тратить на них всю мощь быстрой сортировки. Боб Седжвик разработал весьма хитроумную реализацию этой идеи. Когда функция быстрой сортировки вызывается для небольшого массива (то есть l и u близки), она не делает ничего. Реализуется это путем замены первого оператора if нашей функции на следующий код:

if u-l > cutoff return

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

Для решения задачи сортировки целиком придется выполнить два вызова:

На последнем этапе оптимизации программы можно раскрыть вызов функции swap во внутреннем цикле (поскольку другие два вызова swap лежат вне внутреннего цикла, их раскрытие не даст ощутимого результата). Последняя версия программы Quicksort примет вид:

В табл. 11.2 приведены сводные данные по всем версиям быстрой сортировки. Правая колонка указывает среднее время работы в наносекундах, требуемое для сортировки массива из n случайных целых чисел. Многие алгоритмы могут вести себя как квадратичные для некоторых конкретных входных данных.

Функция qsort состоит из 15 строк быстрой сортировки и 5 строк сортировки вставкой. Для миллиона случайных чисел время выполнения лежит в диапазоне от 0,6 с для библиотечной функции sort языка C++ до 2,7 с для библиотечной функции qsort языка С.
. «

Быстрая сортировка — один из лучших методов сортировки массивов

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

Понятие быстрой сортировки

Быстрая сортировка — Quick Sort или qsort. По названию становится понятно, что это и для чего. Но если не понятно, то это алгоритм по быстрой сортировке массива, алгоритм имеет эффективность O(n log n) в среднем. Что это значит? Это значит, что среднее время работы алгоритма повышается по той же траектории, что и график данной функции. В некоторых популярных языках имеются встроенные библиотеки с этим алгоритмом, а это уже говорит о том, что он крайне эффективен. Это такие языки, как Java, C++, C#.

Алгоритм

Метод быстрой сортировки использует рекурсию и стратегию «Разделяй и властвуй».

1. В массиве ищется некий опорный элемент, для простоты лучше взять центральный, но если вы хотите поработать над оптимизацией, то придётся попробовать разные варианты.

2. Слева от опоры ищется элемент больший, чем опорный, справа — меньший, чем опорный, затем меняем их местами. Делаем это, пока максимальный справа не будет меньше, чем минимальный слева. Таким образом, все маленькие элементы кидаем в начало, большие — в конец.

3. Рекурсивно применяем данный алгоритм к левой и правой части нашего алгоритма отдельно, затем ещё и ещё, до достижения одного элемента или определённого количества элементов. Что же это за количество элементов? Есть ещё один способ оптимизировать данный алгоритм. Когда сортируемая часть становится примерно равной 8 или 16, то можно обработать её обычной сортировкой, например пузырьковой. Так мы повысим эффективность нашего алгоритма, т.к. маленькие массивы он обрабатывает не так быстро, как хотелось бы.

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

Эффективность быстрой сортировки

Является ли быстрая сортировка самым быстрым алгоритмом сортировки? Однозначно нет. Сейчас появляется всё больше и больше сортировок, на данный момент самая быстрая сортировка — это Timsort, она работает крайне быстро для массивов, изначально отсортированных по-разному. Но не стоит забывать, что метод быстрой сортировки является одним из самых простых в написании, это очень важно, ведь, как правило, для рядового проекта нужно именно простое написание, а не громадный алгоритм, который сам ты и не напишешь. Timsort — тоже не самый сложный алгоритм, но звание самого простого ему точно не светит.

Реализация алгоритма

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

Наш метод называется quickSort. В нём запускается основной алгоритм, в который мы передаём массив, первый и последний его элементы. Запоминаем в переменные i и k первый и последний элемент сортируемого отрезка, чтобы не изменять эти переменные, так как они нам нужны. Затем проверяем расстояние между первым и последним проверяемым: оно больше или равно единице? Если нет, значит, мы пришли к центру и нужно выйти из сортировки этого отрезка, а если да, то продолжаем сортировку.

Затем за опорный элемент берём первый элемент в сортируемом отрезке. Следующий цикл делаем до того момента, пока не дойдём до центра. В нём делаем ещё два цикла: первый — для левой части, а второй — для правой. Их мы выполняем, пока есть элементы, подходящие под условие, или пока не дойдём до опорного элемента. Затем, если минимальный элемент всё же справа, а максимальный — слева, меняем их местами. Когда цикл заканчивается, меняем первый элемент и опорный, если опорный меньше. Затем мы рекурсивно делаем наш алгоритм для правого и левого участка массива и так продолжаем, пока не дойдём до отрезка длиной в 1 элемент. Тогда все наши рекурсивные алгоритмы будут return, и мы полностью выйдем из сортировки. Также внизу имеется метод swap — вполне стандартный метод при сортировке массива заменами. Чтобы несколько раз не писать замену элементов, пишем один раз и меняем элементы в данном массиве.

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

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

Быстрая сортировка использует технику “разделяй и властвуй”, чтобы получить те же преимущества, что и сортировка слиянием, но при этом не использовать дополнительное место. Однако, ценой за это станет то, что список может не поделиться пополам, приводя к уменьшению производительности.

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

Рисунок 12 показывает, как 54 выступает в роли первого опорного значения. Поскольку мы уже рассматривали этот пример несколько раз, то знаем, что 54 в итоге окажется на позиции, занятой сейчас 31. Далее происходит процесс разделения. Он находит точку разделения и одновременно перемещает элементы по соответствующим сторонам списка, в зависимости от того, больше они или меньше опорной величины.

Рисунок 12: Первая опорная величина для быстрой сортировки

Разбиение начинается с определения двух маркеров положения — назовём их leftmark и rightmark — в начале и в конце оставшихся элементов списка (позиции 1 и 8 на рисунке 13). В процессе разбиения элементы, лежащие по неправильным сторонам от опорного, должны перемещаться пока маркеры не сойдутся в точке разделения. Рисунок 13 показывает этот процесс для опорного значения 54.

Рисунок 13: Поиск точки разделения для 54

Мы начинаем с увеличения на единицу leftmark , пока не находим значение, большее опорного. Тогда мы уменьшаем на единицу rightmark , пока не находим значение, меньшее опорного. В этот момент мы имеем два элемента, находящихся не на своих местах относительно итоговой точки разбиения. В нашем примере таковыми являются 93 и 20. Теперь можно поменять их местами и повторить процесс заново.

Когда rightmark становится меньше leftmark , мы останавливаемся. Позиция rightmark в данный момент — точка разбиения. Опорное значение следует поменять местами с её содержимым, и тогда оно будет стоять на своём месте (рисунок 14). В дополнение, все элементы слева от точки разбиения теперь меньше опорного значения, а справа — больше. Список поделен на две части, и быстрая сортировка может быть рекурсивно применена к каждой из них.

Рисунок 14: Завершение процесса с целью поиска точки разбиения для 54

Функция quickSort , показанная в CodeLens 7, вызывает другую рекурсивную функцию — quickSortHelper . Она начинает работать с базового случая, аналогичного сортировке слиянием. Если длина списка меньше или равна единице, то он уже отсортирован. Если больше, то он может быть разделен и рекурсивно отсортирован. Функция partition воплощает описанный ранее процесс.

Быстрая сортировка (lst_quick)

Для большей детализации, CodeLens 7 помогут вам пошагово пройти весь алгоритм.

Трассировка быстрой сортировки (quicktrace)

Для анализа функции quickSort стоит отметить, что для списка длиной \(n\) (если деление приходится на его середину) мы вновь получим \(\log n\) разделений. Чтобы найти точку разбиения, каждый из \(n\) элементов нуждается в сравнении с опорным значением. Результатом станет \(n\log n\) . При этом не требуется дополнительной памяти, как в сортировке слиянием.

К сожалению, в наихудшем случае точка разбиения может быть не посередине, а скакать слева направо, делая разделение очень неравномерным. В этом случае сортировка списка из \(n\) элементов разделится на сортировку списков размером 0 и \(n-1\) элементов. Далее сортировка списка длиной \(n-1\) опять даст подсписки из 0 и \(n-2\) элементов, и так далее. Результат: \(O(n^<2>)\) со всеми накладными расходами, требуемыми для рекурсии.

Ранее мы упоминали, что есть несколько способов выбора опорного значения. В частности, мы можем попытаться сгладить потенциальный дисбаланс в разбиении с помощью метода, называемого медианой трёх. Чтобы выбрать опорное значение, мы рассматриваем первый, средний и последний элементы списка. В нашем примере это будут 54, 77 и 20. Теперь определим из них медиану — 54 в данном случае — и возьмём её в качестве опоры (естественно, это было опорное значение, которое мы использовали первоначально). Идея в том, что когда первый элемент списка не принадлежит его середине, медиана трёх станет лучшим “срединным” значением. Особенно это полезно, если первоначальный список уже подвергался частичной сортировке. Мы оставляем реализацию такого выбора опорного значения в качестве упражнения для вас.

dev64

Programming

Быстрая сортировка (Quicksort)

Галерея

Продолжаю просмотр курса «Алгоритмы и структуры данных» от MIT: http://videolectures.net/mit6046jf05_leiserson_lec04/ Сегодня quicksort.

Несколько дополнительных ссылок

Быстрая сортировка заключается в рекурсивном делении сортируемого массива данных на 2 части: большую либо равную значению некоторого элемента, называемого pivot, и меньшую либо равную, чем pivot.

Ниже исходный код на java, демонстрирующий реализацию быстрой сортировки.

Основная работа выполняется в функции partition. Эта функция выполняет в один проход по массиву разбиение массива на 2 части (как показано на картинке выше).

В данном случае в качестве pivot берется элемент из середины массива. Скорость работы быстрой сортировки зависит от значения pivot, выбираемого на каждом шаге. Чтобы глубина рекурсии была наименьшей, нужно чтобы pivot попадал в медианное значение. Тогда на каждом шаге сортировки массив будет делиться на 2 примерно равные части. Это приводит к сложности алгоритма O(n * lg n). В худшем случае, если на каждом шаге в качестве pivot выберется наибольшее или наименьшее значение, тогда глубина рекурсии будет равна n, соответственно будет n рекурсивных проходов по всему массиву размером n. Отсюда сложность в худшем случае достигает O(n^2). В среднем сложность алгоритма O(n * lg n).

Для данного алгоритма при «плохих» случаях глубина рекурсии достигает n, что может вызвать переполнение стека при огромных данных, поэтому для огромных массивов полезно комбинировать Quick Sort с Merge Sort (Сортировка слиянием), а для небольших массивов с Insertion Sort (сортировка вставкой).

Илон Маск рекомендует:  Как выровнять текст по центру
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL