Быстрая сортировка хоара реферат

Обновлено: 17.05.2024

Сортировка Шелла была названа в честь ее изобретателя – Дональда Шелла, который опубликовал этот алгоритм в 1959 году. Общая идея сортировки Шелла состоит в сравнении на начальных стадиях сортировки пар значений, расположенных достаточно далеко друг от друга в упорядочиваемом наборе данных. Такая модификация метода сортировки позволяет быстро переставлять далекие неупорядоченные пары значений ( сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов).

Общая схема метода состоит в следующем.

Шаг 1. Происходит упорядочивание элементов n/2 пар (x_i,x_n/2+i) для 1 .

Шаг 2. Упорядочиваются элементы в n/4 группах из четырех элементов (x_i,x_n/4+i,x_n/2+i,x_3n/4+i) для 1 .

Шаг 3. Упорядочиваются элементы уже в n/4 группах из восьми элементов и т.д.

На последнем шаге упорядочиваются элементы сразу во всем массиве x₁,x₂. x_n . На каждом шаге для упорядочивания элементов в группах используется метод сортировки вставками ( рис. 42.2).

В настоящее время неизвестна последовательность h_i,h_i-1,h_i-2. h₁ ,, оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что h_i+1=3h_i+1 , а h₁=1 . Начинается процесс с h_m , что h_m>[n/9] . Иногда значение h вычисляют проще: h_i+1=h_i/2,h₁=1,h_m=n/2 . Это упрощенное вычисление h и будем использовать далее.

Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту.

Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O(n 1.25 ) , для худшего случая оценкой является O(n 1.5 ) .

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

Метод быстрой сортировки был впервые описан Ч.А.Р. Хоаром в 1962 году. Быстрая сортировка – это общее название ряда алгоритмов, которые отражают различные подходы к получению критичного параметра, влияющего на производительность метода.

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

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

Алгоритм быстрой сортировки Хоара

Пусть дан массив x[n] размерности n .

Шаг 1. Выбирается опорный элемент массива.

Шаг 2. Массив разбивается на два – левый и правый – относительно опорного элемента. Реорганизуем массив таким образом, чтобы все элементы, меньшие опорного элемента, оказались слева от него, а все элементы, большие опорного – справа от него.

Шаг 3. Далее повторяется шаг 2 для каждого из двух вновь образованных массивов. Каждый раз при повторении преобразования очередная часть массива разбивается на два меньших и т. д., пока не получится массив из двух элементов ( рис. 42.3).

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

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

Эффективность быстрой сортировки в значительной степени определяется правильностью выбора опорных (ведущих) элементов при формировании блоков. В худшем случае трудоемкость метода имеет ту же сложность, что и пузырьковая сортировка , то есть порядка O(n 2 ) . При оптимальном выборе ведущих элементов, когда разделение каждого блока происходит на равные по размеру части, трудоемкость алгоритма совпадает с быстродействием наиболее эффективных способов сортировки, то есть порядка O(n log n) . В среднем случае количество операций, выполняемых алгоритмом быстрой сортировки, определяется выражением T(n) = O(1.4n log n)

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

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

Алгоритм называется вероятностным (randomized), если он использует генератор случайных чисел (random-number generator). Мы будем считать, что генератор случайных чисел Random работает так: RANDOM (a, b) возвращает с равной вероятностью любое целое число в интервале от, а до b. Например. Random (0,1) возвращает 0 или 1 с вероятностью ½. При этом разные вызовы процедуры независимы в смысле теории… Читать ещё >

Алгоритм быстрой сортировки ( реферат , курсовая , диплом , контрольная )

Кафедра информатики и методики преподавания информатики Курсовая работа Алгоритм быстрой сортировки Выполнила:

студентка 3 курса 1 группы физико-математического факультета Савенко Елена Николаевна Научный руководитель:

Доцент кафедры информатики и методики преподавания информатики, кандидат физико — математических наук Сергиевич Николай Владимирович Мозырь 2007

Глава 1. Основные теоретические аспекты алгоритма и сортировки

1.1 Понятие алгоритма и сортировки

Алгоритм (algorithm) — это любая корректно определенная вычислительная процедура, на вход (input), которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений. Таким образом, алгоритм представляет собой последовательность вычислительных шагов, преобразующих входные величины в выходные.

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

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

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список L из n элементов будет отсортирован в порядке возрастания значений элементов, если L1 и т. д. до обмена двух последних элементов.

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

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

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

Метод быстрой сортировки был разработан в 1960 году Ч. Ф. Р. Хоаром (C.A.R.Hoare) и он же дал ему это название. В настоящее время этот метод сортировки считается наилучшим. Он основан на использовании обменного метода сортировки. Это тем более удивительно, если учесть очень низкое быстродействие сортировки пузырьковым методом, который представляет собой простейшую версию обменной сортировки.

исходное состояние: 7 356 821;

первый проход: 2 135 687;

второй проход: 1 235 678.

Однако следует иметь в виду одно неприятное свойство быстрой сортировки. Если выбираемое для разбиения значение оказывается совпадающим с максимальным значением, то быстрая сортировка превращается в самую медленную с временем выполнения n. Однако на практике этот случай не встречается.

1.4 Основные правила, понятия и теоремы

Обозначим через T (n) время решения задачи, размер которой равен n. Если размер задачи достаточно мал, скажем, n? с, где с — некоторая заранее известная константа, то задача решается непосредственно в течение определенного фиксированного времени, которое мы обозначим через ?(1). Предположим, что наша задача делится на a подзадач, объем каждой из которых равен 1/b от объема исходной задачи. Если разбиение задачи на вспомогательные подзадачи происходит в течение времени D (n), а объединение решений подзадач в решение исходной задачи — в течение времени С (n), то мы получим такое рекуррентное соотношение:

Основной метод решения рекуррентных отношений базируется на основной теореме, приведенной ниже.

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

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

1. Если для некоторой константы, то .

3. Если для некоторой константы, и если для некоторой константы и всех достаточно больших n, то .

Правило 1. Арифметическая прогрессия.

является арифметической прогрессией и ее значение равно:

Правило 2. Разбиение на части.

Можно разбить сумму на части и оценивать их по отдельности. В качестве примера возьмем сумму. Получим

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

· Отступ от левого поля указывает на уровень вложенности.

· Циклы while, for, repeat и условные конструкции if, then, else имеют тот же смысл, что и в Паскале.

· Символ > начинает комментарий (идущий до конца строки).

· Одновременное присваивание (переменные и получают значение) заменяет два присваивания и (в этом порядке).

· Переменные локальны внутри процедуры (если не оговорено противное).

· Часто используются объекты, состоящие из нескольких полей, или, как говорят, имеющие несколько атрибутов. Значение поля записывается как имя_поля [имя_объекта]. Например, длина массива считается его атрибутам и обозначается length, так что длина массива запишется как length. Из контекста обычно ясно, что именно обозначают квадратные скобки (элемент массива или поле объекта).

Переменная, обозначающая объект или массив, считается указателем на составляющие его данные. После присваивания для любого поля выполнено .

· Параметры передаются по значению: вызванная процедура получает собственную копию параметров; изменение параметра внутри процедуры снаружи невидимо. При передаче объектов копируется указатель на данные составляющие этот объект, а сами поля объекта — нет.

Сортировка участка, А [p.r] происходит так:

· Элементы массива, А переставляются так, чтобы любой из элементов А[р]…А[q] был не больше любого из элементов, А [q+1]…A[r], где q — некоторое число в интервале р=

· Процедура сортировки рекурсивно вызывается для массивов A[p.q] и A[q+l.r].

После этого массив, А [р…r] отсортирован.

Итак, процедура сортировки QUICKSORT выглядит следующим образом:

3. Quicksort (p, q)

4. Quicksort (q+ 1, r)

Ключевой частью рассматриваемого алгоритма сортировки является функция Part, изменяющая порядок элементов массива, А [р.r] без привлечения дополнительной памяти.

Создадим цикл, в котором найдем элементы виде A[j] =x. Для этого мы будем уменьшать j пока A[j] =x. Затем, сравнивая i и j, посмотри, где находятся наши элементы в массиве A[p.i] или в массиве A[j.r]. Затем проверим выполняется ли неравенство i

Хотя идея функции очень проста, сам алгоритм содержит ряд тонких моментов. Например, не очевидно, что индексы i и j не выходят за границы промежутка [р.r] в процессе работы. Другой пример: важно, что в качестве граничного значения выбирается, А [р], а не, скажем, A[r]. В последнем случае может оказаться, что A[r] - самый большой элемент массива, и в конце выполнения процедуры будет i=j=r, так что возвращать j функции будет нельзя — нарушится требование q

Время работы функции Part составляет, где .

2.2 Реализация на языке программирования

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

Процедуры read и write используются для ввода и вывода данных.

Reset — процедура, открывающая файл для чтения.

Assign — процедура, предназначенная для связывания файловой переменной с файлом на диске.

Rewrite — процедура, открывающая файл для записи. Если файла не существует, то она создает его.

Close — процедура, закрывающая открытый файл.

A:array [1.n] of integer;

assign (input,'input.txt'); reset (input);

assign (output,'output.txt'); rewrite (output);

С помощью оператора For прочтем массив из файла.

for k:=1 to n do read (A[k]);

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

procedure QuickSort (p, r: integer);

Эта переменная будет являться тем средним значением, которое мы получим в результате функции Part (ее опишем ниже). Затем процедура Quicksort вызывает саму себя уже для подмассивов [р.q] и [q+l.r].

Но это все будет выполняться, если будет выполняться условие p

В этой процедуре используется функция Part, которая так же имеет свои переменные:

function Part (p, r: integer):integer;

var c, x, j, i, q:integer;

Эта функция сортирует массив с помощью нескольких операторов. Но для начала нам необходимо ввести два накопителя, которые сразу пусты. И введем некоторое значение x.

С помощью оператора while мы будем повторять следующие действия.

while true do begin

И так, для начала мы будем уменьшать j, пока A[j]>=x:

И увеличивать i, пока A[i]>=x:

Проверим условие i

После этого мы присваиваем значение j самой функции Part.

Глава 3. Анализ быстрой сортировки

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

3.1 Анализ наихудшего разбиения

(последняя сумма — арифметическая прогрессия, см. правило 1). Дерево рекурсии для этого случая показано на рис. 1.

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

Для доказательства того, что время работы составляет, мы используем метод подстановки (смотри правило 3). Пусть — наибольшее время работы алгоритма для массива длины n. Тогда, очевидно

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

Квадратный трёхчлен достигает максимума на отрезке в его концах, т. к. вторая производная по q положительна и функция выпукла вниз. Этот максимум равен. Отсюда получаем

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

3.2 Наилучшее разбиение

алгоритм сортировка хоар программирование

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

и, согласно теореме 1,. Дерево рекурсии для этого случая показано на рисунке 2.

3.3 Промежуточный случай

Предположим, что среднее время работы (с точностью до множителя) совпадает со временем работы в наилучшем случае. Чтобы объяснить это, посмотрим, как меняется рекуррентное соотношение в зависимости, от степени сбалансированности разбиения.

Пусть, например, на каждом шаге массив разбивается на две части с отношением размеров 9:1. Тогда

(для удобства мы заменили на). Дерево рекурсии показано на рисунке 3. На каждом уровне мы производим не более n действии, так что время работы определяется глубиной рекурсии.

В данном случае эта глубина равна, так что время работы по-прежнему составляет ?(nlgn), хотя константа и больше. Ясно, что для любого фиксированного отношения размеров частей (сколь бы велико оно ни было) глубина дерева рекурсии по-прежнему будет логарифмической, а время работы будет равно ?(nlgn).

3.4 Вероятностные алгоритмы быстрой сортировки

Ранее мы предположили, что все перестановки входных значений равновероятны. Если это так, а размер массива достаточно велик, быстрая сортировка — один из наиболее эффективных алгоритмов. На практике, однако, это предположение не всегда оправдано.

Теперь мы введём понятие вероятностного алгоритма и рассмотрим два вероятностных алгоритма быстрой сортировки, которые позволяют отказаться от предположения о равной вероятности всех перестановок.

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

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

Вместо того, чтобы предварительно переставлять элементы массива, мы можем внести элемент случайности в функцию Part. Именно, перед разбиением массива, А [p.r] будем менять элемент А[р] со случайно выбранным элементом массива. Тогда каждый элемент с равной вероятностью может оказаться граничным, и в среднем разбиения будут получаться достаточно сбалансированными.

Этот подход заменяет разовую случайную перестановку входов в начале использованием случайных выборов на всём протяжении работы алгоритма. В сущности это то же самое, и оба алгоритма имеют математическое ожидание времени работы O (n lgn), но небольшие технические различия делают анализ нового варианта проще, и именно его мы будем рассматривать далее.

Изменения, которые нужно внести в процедуры, совсем неволики:

поменять А[р] f-> A[i]

return Partition (Л. р, г)

В основной процедуре теперь будет использоваться Randomized-Partition вместо Partition:

Randomized-Quicksort (A, р. г)

2 then q *- Randomized-Partition (A, p, г)

Randomized-Quicksort (A. p, q)

Randomized-Qijicksort (A, q + 1, r)

3.5 Нахождение и анализ среднего времени работы сортировки

3.5.1 Интуитивные соображения по нахождению среднего времени

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

Для наугад взятого массива разбиения вряд ли будут всё время происходить в одном и том же отношении — скорее всего, часть разбиений будет хорошо сбалансирована, а часть нет, примерно 80 процентов разбиений производятся в отношении не более 9:1.

Рис. 4. Два уровня плохой (n разбивается на n-1 и 1) и хороший (n-1 разбивается на две равные части).

3.5.2 Анализ среднего времени работы

Анализ разбиений.

Напомним, что перед тем как в функции Rand-Part вызывается функция Part, элемент А[р] переставляется со случайно выбранным элементом массива, А [p.r]. Для простоты мы будем предполагать, что все числа в массиве различны. Хотя оценка среднего времени сохраняется и в том случае, когда в массиве есть одинаковые элементы, получить ее сложнее, и мы этого делать не будем.

Прежде всего, заметим, что значение q, которое возвратит функция Part, зависит только от того, сколько в массиве элементов, не больших x= А[р]. Число таких элементов мы будем называть рангом элемента x и обозначать rank (x). Если n число элементов массива, то, поскольку все элементы имеют равные шансы попасть на место А[р], все значения rank (x), от 1 до n, равновероятны и имеют вероятность 1/n.

Если rank (x)>1. то, как легко видеть, при разбиении левая часть будет содержать rank (x)-1 элементов — в ней окажутся все элементы, меньше x. Если же rank (x)=1, то левая часть будет содержать один элемент. Отсюда следует, что с вероятностью 1/n левая часть будет содержать 2,3,…, n-1 элементов, а с вероятностью 2/n — один элемент.

Рекуррентное соотношение для среднего времени работы.

Обозначим среднее время работы алгоритма Rand-Part для массива из n элементов через. Ясно, что. Время работы состоит из времени работы функции Part, которое составляет, и времени работы для двух массивов размеров и, причем с вероятностью 2/n принимает значения 1 и с вероятностью 1/n значения 2, 3,…, n-1. Поэтому

Слагаемое, соответствующее q=1, входит дважды и поскольку и, имеем

Поэтому слагаемые и в первой скобке (1) можно включить в. С учетом этого получаем

Поскольку каждое слагаемое, где k=1, 2,…, n-1, встречается в сумме дважды, ее можно переписать так:

Решение рекуррентного соотношения.

Соотношение 2 можно решить, используя метод подстановки. Предположим, что, где константы и пока неизвестны, и попытаемся доказать это по индукции. При n=1 это верно, если взять достаточно большие, а и b. При n>1 имеем

Ниже мы покажем, что первую сумму можно оценить так:

Используя это, получим

Если выбрать, а так, чтобы аn/4 было больше. Следовательно, среднее время работы есть .

Доказательство оценки для суммы.

Нам осталось доказать оценку (3). Поскольку каждое слагаемое не превышает nlgn, получаем оценку

Для наших целей она не подходит — нам необходимо более точная оценка .

Если, заменив лишь на, мы, оставив k в неприкосновенности, получим оценку

Осталось лишь заметить, что заменяя на, мы прибавили, по крайней мере по k к каждому слагаемом первой половины суммы (где kn/2), всего примерно .

ГОСТ

Алгоритм быстрой сортировки — это наиболее известный алгоритм сортировки информационных данных, изобретённый Т. Хоаром.

Введение

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

Алгоритм быстрой сортировки

Алгоритм быстрой сортировки выполняется следующим образом:

Готовые работы на аналогичную тему

Выбор опорного элемента

В начале использования алгоритма быстрой сортировки в качестве опорного служил первый элемент. Это могло существенно снижать эффективность сортировки. Лучшие результаты даёт выбор медианного, то есть среднего элемента, что является оптимальным вариантом. Но нахождение такого элемента требует значительных вычислительных ресурсов. Более простой способ определения опорного элемента предложил Ломуто, и он был описан в популярных изданиях. В качестве опорного берётся последний элемент, а в алгоритме сохраняется индекс в специальной переменной. В случае нахождения элемента, который меньше или равен опорному, выполняется увеличение индекса и данный элемент ставится впереди опорного. Данная методика разбиения менее громоздка, чем у Т. Хоара, но и не такая эффективная. Если массив уже прошёл сортировку или имеет равные по величине компоненты, то быстрая сортировка становится менее сложной. Есть разные методы, которые позволяют оптимизировать эту сортировку.

Разбиение Хоара

Эта методика применяет индекс в начале массива и ещё один в его конце. Индексы движутся во встречном направлении до тех пор, пока не обнаружатся два элемента, один из которых больше опорного и располагается перед ним, а второй меньше опорного и располагается за ним. Найденные элементы следует поменять местами, и такие обмены выполняются до момента пересечения индексов. Затем согласно алгоритму, возвращается последний индекс. Эта методика Т. Хоара имеет большую эффективность, чем схема Ломуто, поскольку среднее количество обменных операций примерно в три раза меньше, и она эффективнее даже при равенстве всех элементов. Но следует заметить, что данная методика сортировки нестабильна.

Сложность алгоритма

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

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

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

Быстрая сортировка (англ. quicksort ), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

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

Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:

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

O(n log n) (обычное разделение)
или O(n) (разделение на 3 части)

O(n log n)

O(n) вспомогательных
O(log n) вспомогательных

Реализация алгоритма на различных языках программирования:

Работает для произвольного массива из n целых чисел.

Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.

Быстрая сортировка на основе библиотеки STL.

Java, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива)

JavaScript

Python

С использованием генераторов:

Haskell

Математическая версия — с использованием генераторов:

Common Lisp

В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" - она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует "императивные" макросы Common Lisp'а.

Pascal

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

Устойчивый вариант (требует дополнительно O(n)памяти)

Быстрая сортировка, нерекурсивный вариант

Нерекурсивная реализация быстрой сортировки через стек. Функции compare и change реализуются в зависимости от типа данных.

Читайте также: