Цель: изучение алгоритма быстрой сортировки и ее модификаций.
На этом занятии мы изучим алгоритм быстрой сортировки, который, пожалуй, используется более часто, чем любой другой. Основа алгоритма была разработана в 1960 году (C.A.R.Hoare) и с тех пор внимательно изучалась многими людьми. Быстрая сортировка особенно популярна ввиду легкости ее реализации; это довольно хороший алгоритм общего назначения, который хорошо работает во многих ситуациях, и использует при этом меньше ресурсов, чем другие алгоритмы.
Основные достоинства этого алгоритма состоят в том, что он точечный (использует лишь небольшой дополнительный стек), в среднем требует только около N log N операций для того, чтобы отсортировать N элементов, и имеет экстремально короткий внутренний цикл. Недостатки алгоритма состоят в том, что он рекурсивен (реализация очень затруднена когда рекурсия недоступна), в худшем случае он требует N2 операций, кроме того он очень "хрупок": небольшая ошибка в реализации, которая легко может пройти незамеченной, может привести к тому, что алгоритм будет работать очень плохо на некоторых файлах.
Производительность быстрой сортировки хорошо изучена. Алгоритм подвергался математическому анализу, поэтому существуют точные математические формулы касающиеся вопросов его производительности. Результаты анализа были неоднократно проверены эмпирическим путем, и алгоритм был отработан до такого состояния, что стал наиболее предпочтительным для широкого спектра задач сортировки. Все это делает алгоритм стоящим более детального изучения наиболее эффективных путей его реализации. Похожие способы реализации подходят также и для других алгоритмов, но в алгоритме быстрой сортировки мы можем использовать их с уверенностью, поскольку его производительность хорошо изучена.
Улучшить алгоритм быстрой сортировки является большим искушением: более быстрый алгоритм сортировки - это своеобразная "мышеловка" для программистов. Почти с того момента, как Oia?a впервые опубликовал свой алгоритм, в литературе стали появляться "улучшенные" версии этого алгоритма. Было опробовано и проанализировано множество идей, но все равно очень просто обмануться, поскольку алгоритм настолько хорошо сбалансирован, что результатом улучшения в одной его части может стать более сильное ухудшение в другой его части. Мы изучим в некоторых деталях три модификации этого алгоритма, которые дают ему существенное улучшение.
Хорошо же отлаженная версия быстрой сортировки скорее всего будет работать гораздо быстрее, чем любой другой алгоритм. Однако стоит еще раз напомнить, что алгоритм очень хрупок и любое его изменение может привести к нежелательным и неожиданным эффектам для некоторых входных данных.
Суть алгоритма: число операций перемены местоположений элементов внутри массива значительно сократится, если менять местами далеко стоящие друг от друга элементы. Для этого выбирается для сравнения один элемент х, отыскивается слева первый элемент, который не меньше х, а справа первый элемент, который не больше х. Найденные элементы меняются местами. После первого же прохода все элементы, которые меньше х, будут стоять слева от х, а все элементы, которые больше х, - справа от х. С двумя половинами массива поступают точно также. Продолжая деление этих половин до тех пор пока не останется в них по 1 элементу.
Program Quitsort;
uses
crt;
Const
N=10;
Type
Mas=array of integer;
var
a: mas;
k: integer;
function Part(l, r: integer):integer;
var
v, i, j, b: integer;
begin
V:=a[r];
I:=l-1;
j:=r;
repeat
repeat
dec(j)
until (a[j]<=v) or (j=i+1);
repeat
inc(i)
until (a[i]>=v) or (i=j-1);
b:=a[i];
a[i]:=a[j];
a[j]:=b;
until i>=j;
a[j]:=a[i];
a[i]:= a[r];
a[r]:=b;
part:=i;
end;
procedure QuickSort(l, t: integer);
var i: integer;
begin
if l 60,79, 82, 58, 39, 9, 54, 92, 44, 32
60,79, 82, 58, 39, 9, 54, 92, 44, 32
9,79, 82, 58, 39, 60, 54, 92, 44, 32
9,79, 82, 58, 39, 60, 54, 92, 44, 32
9, 32, 82, 58, 39, 60, 54, 92, 44, 79
9, 32, 44, 58, 39, 60, 54, 92, 82, 79
9, 32, 44, 58, 39, 54, 60, 92, 82, 79
9, 32, 44, 58, 39, 92, 60, 54, 82, 79
9, 32, 44, 58, 39, 54, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 60, 39, 54, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 58, 54, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 92, 82
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
"Внутренний цикл" быстрой сортировки состоит только из увеличения указателя и сравнения элементов массива с фиксированным числом. Это как раз и делает быструю сортировку быстрой. Сложно придумать более простой внутренний цикл. Положительные эффекты сторожевых ключей также оказывают здесь свое влияние, поскольку добавление еще одной проверки к внутреннему циклу оказало бы отрицательное влияние на производительность алгоритма. Самая сомнительная черта вышеприведенной программы состоит в том, что она очень мало эффективна на простых подфайлах. Например, если файл уже сортирован, то разделы будут вырожденными, и программа просто вызовет сама себя N раз, каждый раз с меньшим на один элемент подфайлом. Это означает, что не только производительность программы упадет примерно до N2/2, но и пространство необходимое для ее работы будет около N (смотри ниже), что неприемлемо. К счастью, есть довольно простые способы сделать так, чтобы такой "худший" случай не произошел при практическом использовании программы. Когда в файле присутствуют одинаковые ключи, то возникает еще два сомнительных вопроса. Первое, должны ли оба указателя останавливаться на ключах равных делящему элементу или останавливать только один из них, а второй будет проходить их все, или оба указателя должны проходить над ними. На самом деле, этот вопрос детально изучался, и результаты показали, что самое лучшее - это останавливать оба указателя. Это позволяет удерживать более или менее сбалансированные разделы в присутствии многих одинаковых ключей. На самом деле, эта программа может быть слегка улучшена терминированием сканирования j Характеристики Производительности Быстрой Сортировки Самое лучшее, что могло бы произойти для алгоритма - это если бы каждый из подфайлов делился бы на два равных по величине подфайла. В результате количество сравнений делаемых быстрой сортировкой было бы равно значению рекурсивного выражения CN = 2CN/2+N - наилучший случай. (2CN/2 покрывает расходы по сортировке двух полученных подфайлов; N - это стоимость обработки каждого элемента, используя один или другой указатель.) Нам известно также, что примерное значение этого выражения равно CN = N lg N. Хотя мы встречаемся с подобной ситуацией не так часто, но в среднем время работы программы будет соответствовать этой формуле. Если принять во внимание вероятные позиции каждого раздела, то это сделает вычисления более сложными, но конечный результат будет аналогичным. Свойство 1 Быстрая сортировка в среднем использует 2N ln N сравнений. Методы улучшения быстрой сортировки. Первое улучшение в алгоритме быстрой сортировки возникает из наблюдения, что программа гарантировано вызывает себя для огромного количества небольших подфайлов, поэтому следует использовать самый лучший метод сортировки когда мы встречаем небольшой подфайл. Очевидный способ добиться этого, это изменить проверку в начале рекурсивной функции из "if r>l then" на вызов сортировки вставкой (соответственно измененной для восприятия границ сортируемого подфайла): "if r-l<=M then insertion(l, r)." Значение для M не обязано быть "самым-самым" лучшим: алгоритм работает примерно одинаково для M от 5 до 25. Время работы программы при этом снижается примерно на 20% для большинства программ. При небольших подфайлах (5- 25 элементов) быстрая сортировка очень много раз вызывает сама себя (в наше примере для 10 элементов она вызвала сама себя 15 раз), поэтому следует применять не быструю сортировку, а сортировку вставкой. Procedure QuickSort (l,t:integer);
var
i:integer;
begin
if t-l>m then
begin
i:=part(l,t);
QuickSort (l,i-1);
QuickSort (i+1,t);
end
Else
Insert(l,t);
end;
Второе улучшение в алгоритме быстрой сортировки состоит в попытке использования лучшего делящего элемента. У нас есть несколько возможностей. Наиболее безопасная из них будет попытка избежать худшего случая посредством выбора произвольного элемента массива в качестве делящего элемента. Тогда вероятность худшего случая становится пренебрежимо мала. Это простой пример "вероятностного" алгоритма, который почти всегда работает вне зависимости от входных данных. Произвольность может быть хорошим инструментом при разработке алгоритмов, особенно если возможны подозрительные входные данные. Более полезное улучшение состоит в том, чтобы взять из файла три элемента, и затем использовать среднее из них в качестве делящего элемента. Если элементы взяты из начала, середины, и конца файла, то можно избежать использования сторожевых элементов: сортируем взятые три элемента, затем обмениваем центральный элемент с a, и затем используем алгоритм деления на массиве a. Это улучшение называется делением по медиане из трех. Метод деления по медиане из трех полезен по трем причинам. Во-первых, он делает вероятность худшего случая гораздо более низкой. Чтобы этот алгоритм использовал время пропорциональной N2, два из трех взятых элементов должны быть либо самыми меньшими, либо самыми большими, и это должно повторяться из раздела в раздел. Во-вторых, этот метод уничтожает необходимость в сторожевых элементах, поскольку эту роль играет один из трех взятых нами перед делением элементов. В третьих, он на самом деле снижает время работы алгоритма приблизительно на 5%. Procedure exchange(i,j:integer);
var
k:integer;
begin
k:=a[i];
a[i]:=a[j];
a[j]:=k;
end;
procedure Mediana;
var i:integer;
begin
i:=n div 4;{Рис.}
if a[i]>a then
if a[i]>a then
exchange(i,n)
else
exchange(i*3,n)
else
if a>a then
exchange(i*2,n);
quicksort(1,n);
end;
Можно переписать данный алгоритм без использования рекурсии используя стек, но здесь мы это не будем делать. Комбинация нерекурсивной реализации деления по медиане из трех с отсечением на небольшие файлы может улучшить время работы алгоритма от 25% до 30%. Итак, на сегодняшнем занятии мы рассмотрели алгоритм быстрой сортировки. На сегодняшнем занятии мы начнем рассмотрении темы внешняя сортировка. Внешняя сортировка сортирует файлы, которые не помещаются целиком в оперативную память. Внешняя сортировка сильно отличается от внутренней. Дело в том, что доступ к файлу является последовательным, а не параллельным как это было в массиве. И поэтому считывать файл можно только блоками и этот блок отсортировать в памяти и снова записать в файл. Принципиальную возможность эффективно отсортировать файл, работая с его частями и не выходя за пределы части обеспечивает алгоритм слияния. Под слиянием понимается объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Слияние - намного более простая операция, чем сортировка. Мы рассмотрим 2 алгоритма слияния: Последовательность а разбивается на две половины b и с. Последовательности b и с сливаются при помощи объединения отдельных элементов в упорядоченные пары. Полученной последовательности присваивается имя а, после чего повторяются шаги 1 и 2; при этом упорядоченные пары сливаются в упорядоченные четверки. Предыдущие шаги повторяются, при этом четверки сливаются в восьмерки и т.д., пока не будет упорядочена вся последовательность, т.к. длины последовательностей каждый раз удваиваются. Пример
Исходная последовательность А = 44 55 12 42 94 18 06 67
1
b = 44 55 12 42
с = 94 18 06 67
а = 44 94" 18 55" 06 12" 42 67
2
b = 44 94" 18 55"
с =06 12" 42 67
а = 06 12 44 94" 18 42 55 67"
3
b = 06 12 44 94"
с = 18 42 55 67"
а = 06 12 18 42 44 55 67 94
Операция, которая однократно обрабатывает всё множество данных, называется фазой. Наименьший подпроцесс, который, повторяясь, образует процесс сортировки, называется проходом или этапом. В нашем примере сортировка производится за три прохода. Каждый проход состоит из фазы разбиения и фазы слияния. Главным минусом сортировки слиянием является удвоение размера памяти, первоначально занятой сортируемыми данными. Рассмотрим алгоритм с рекурсивным актом слияния, предложенный Боузом и Нельсоном и не требующий резерва памяти. Он основан на очевидной идее: слить две равные упорядоченные части можно слиянием их начальных половин, слиянием конечных и слиянием 2-й половины 1-го результата с 1-й половиной 2-го результата, например: Если части не равны или не делятся точно пополам, процедуру уточняют надлежащим образом. Аналогично слияние "половинок" можно свести к слиянию "четвертушек", "восьмушек" и т. д.; имеет место рекурсия. Const n=200;
Type
tipkl=word;
tip = Record
kl: tipkl;
z:Array of real
End;
Var
A: Array of tip;
j:word;
Procedure Bose (Var AA; voz:Boolean);
Var
m,j:word; x:tip; {tip - тип сортируемых записей}
A: Array of tip Absolute AA;
Procedure Sli(j,r,m: word); { r - расстояние между началами
сливаемых частей, а m - их размер, j - наименьший номер записи}
Begin
if j+r<=n Then
If m=1 Then
Begin
If voz Xor (A[j].kl < A.kl) Then
Begin
x:=A[j];
A[j]:= A;
A:=x
End
End
Else
Begin
m:=m div 2;
Sli(j,r,m); {Слияние "начал"}
If j+r+m<=n Then
Sli(j+m,r,m); {Слияние "концов"}
Sli(j+m,r-m,m) End {Слияние в центральной части}
End{блока Sli};
Begin
m:=1;
Repeat
j:=1; {Цикл слияния списков равного размера: }
While j+m<=n do
Begin
Sli(j,m,m);
j:=j+m+m
End;
m:=m+m {Удвоение размера списка перед началом нового прохода}
Until m >= n {Конец цикла, реализующего все дерево слияний}
End{блока Bose};
BEGIN
Randomize;
For j:=1 to n do
begin
A[j].kl:= Random(65535);
Write(A[j].kl:8);
end;
Readln;
Bose(A,true);
For j:=1 to n do
Write(A[j].kl:8);
Readln
END.
Она объединяются упорядоченные части, спонтанно возникшие в исходном массиве; они могут быть также следствием предыдущей обработки данных. Рассчитывать на одинаковый размер сливаемых частей не приходится. Записи, идущие в порядке неубывания ключей, сцепляются, образуя подсписок. Минимальный подсписок одна запись. Пример:
Пусть даны ключи записей 5 7 8 3 9 4 1 7 6
Ищем подсписки В один общий список соединяются 1-й, 3-й, 5-й и т. д. подсписки, в другой - 2-й, 4-й и т. д. подсписки. Произведем слияние 1 подсписка 1 списка и 1 подсписка 2 списка, 2 подсписка 1 списка и 2 подсписка 2 списка и т.д. Будут получены следующие цепи 3 --> 5 --> 7 --> 8 --> 9 и 1 --> 4 --> 7
Подсписок, состоящий из записи "6", пары не имеет и "принудительно" объединяется с последней цепью, принимающей вид 1 --> 4--> 6 --> 7. При нашем небольшом числе записей 2-й этап, на котором сливаются две цепи, окажется последним. В общем случае на каждом этапе подсписок - результат слияния начальных подсписков 1 и 2 списка становится началом нового 1-го списка, а результат слияния следующих двух подсписков - началом 2-го списка. Следующие образуемые подсписки поочередно включаются в 1-й и во 2-й список. Для программной реализации заводят массив sp: элемент sp[i] - это номер записи, которая следует за i-й. Последняя запись одного подсписка ссылается на первую запись другого, а для различения концов подсписков эта ссылка снабжается знаком минус. Repeat {Повторение актов слияний подсписков}
If A[j].kl < A[i].kl Then {Выбирается меньшая запись}
Begin sp[k]:=j; k:=j; j:=sp[j];
If j<=0 Then {Сцепление с остатком "i"-подсписка}
Begin sp[k]:=i; Repeat m:=i; i:=sp[i] Until i<=0 End
End
Else
Begin sp[k]:=i; k:=i; i:=sp[i];
If i<=0 Then {Сцепление с остатком "j"-подсписка}
Begin sp[k]:=j; Repeat m:=j; j:=sp[j] Until j<=0 End
End;
If j<=0 Then Begin sp[m]:= 0; sp[p]:=-sp[p]; i:=-i;
j:=-j; If j<>0 Then p:=r; k:=r; r:=m End
Until j=0;
{В конец сформированного подсписка всегда заносится нулевая ссылка (sp[m]:= 0), ибо он может оказаться последним. Действие sp[p]:= -sp[p] обозначает минусом конец ранее построенного подсписка. Итак, на сегодняшнем занятии мы рассмотрели алгоритмы слияния. А
лгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за 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, а правая - длина массива минус один. Нам понадобятся следующие переменные Size_t i, j;
указывают на левый и правый элементы, Int tmp, pivot;
первая переменная для обмена при сортировке, вторая будет хранить значение опорного элемента. Сначала задаём начальные значения I = low;
j = high;
pivot = a[(low + (high-low)/2)];
Здесь следует сразу же оговориться. Выбирать всегда средний элемент в качестве опорного – достаточно рискованно. Если известно, какой элемент будет выбран в качестве опорного,
то можно подобрать такую последовательность, для которой сортировка будет происходить максимально медленно, за время порядка n 2 .
Поэтому в качестве элемента, относительно которого будет сортировка, берут либо случайный элемент, либо медиану из первого, последнего и среднего элементов. Пока i будет меньше j (пока они не пересекутся) делаем следующее. Во первых, нужно пропустить все уже отсортированные элементы Do {
while (a[i] < pivot) {
i++;
}
while (a[j] > pivot) {
j--;
}
If (i <= j) {
if (a[i] > a[j]) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
i++;
j--;
}
} while (i <= j);
Здесь, однако, возможна ошибка. i вряд ли переполнится - размер массива не больше, чем максимальное значение типа size_t, умноженное на размер элемента массива байт (более сложные варианты даже рассматривать не будем).
Но вот переменная j вообще-то может перейти через нуль. Так как переменная целочисленная, то при переходе через нуль её значение станет больше, чем i, что приведёт к зацикливанию. Поэтому необходима превентивная проверка. If (j > 0) {
j--;
}
После этого цикла i и j пересекутся, i станет больше j и мы получим ещё два массива, для которых следует применить сортировку: массив от левой границы до i, и массив от j до правой границы, если, конечно, мы не вышли за пределы границ. If (i < high) {
qsortx(a, i, high);
}
if (j > low) {
qsortx(a, low, j);
}
Void qsortx(int *a, size_t low, size_t high) {
size_t i, j;
int tmp, pivot;
i = low;
j = high;
pivot = a[(low + (high-low)/2)];
do {
while (a[i] < pivot) {
i++;
}
while (a[j] > pivot) {
j--;
}
if (i <= j) {
if (a[i] > a[j]) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
i++;
if (j > <= j);
if (i < high) {
qsortx(a, i, high);
}
if (j > low) {
qsortx(a, low, j);
}
}
Функция называется qsortx, чтобы не спутать со стандартной функцией быстрой сортировки qsort. Теперь вместо того, чтобы вызывать функцию, будем сохранять в стек крайнее левое и правое значения. Можно сохранять сразу пару значений, но мы вместо этого сделаем два параллельных стека. В первый будем класть крайнее левое значение для следующего вызова, а во второй - крайнее правое. Цикл заканчивается, когда стеки становятся пустыми. Void qsortxi(int *a, size_t size) {
size_t i, j;
int tmp, pivot;
Stack *lows = createStack();
Stack *highs = createStack();
size_t low, high;
push(lows, 0);
push(highs, size - 1);
while (lows->size > 0) {
low = pop(lows);
high = pop(highs);
i = low;
j = high;
pivot = a[(low + (high-low)/2)];
do {
while (a[i] < pivot) {
i++;
}
while (a[j] > pivot) {
j--;
}
if (i <= j) {
if (a[i] > a[j]) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
i++;
if (j > 0) {
j--;
}
}
} while (i <= j);
if (i < high) {
push(lows, i);
push(highs, high);
}
if (j > low) {
push(lows, low);
push(highs, j);
}
}
freeStack(&lows);
freeStack(&highs);
}
Код стека
#define STACK_INIT_SIZE 100
typedef struct Stack {
size_t size;
size_t limit;
int *data;
} Stack;
Stack* createStack() {
Stack *tmp = (Stack*) malloc(sizeof(Stack));
tmp->limit = STACK_INIT_SIZE;
tmp->size = 0;
tmp->data = (int*) malloc(tmp->limit * sizeof(int));
return tmp;
}
void freeStack(Stack **s) {
free((*s)->data);
free(*s);
*s = NULL;
}
void push(Stack *s, int item) {
if (s->size >= s->limit) {
s->limit *= 2;
s->data = (int*) realloc(s->data, s->limit * sizeof(int));
}
s->data = item;
}
int pop(Stack *s) {
if (s->size == 0) {
exit(7);
}
s->size--;
return s->data;
}
Функция в общем виде Void qsortxig(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
size_t i, j;
void *tmp, *pivot;
Stack *lows = createStack();
Stack *highs = createStack();
size_t low, high;
push(lows, 0);
push(highs, size - 1);
tmp = malloc(item);
while (lows->size > 0) {
low = pop(lows);
high = pop(highs);
i = low;
j = high;
pivot = (char*)a + (low + (high-low)/2)*item;
do {
while (cmp(((char*)a + i*item), pivot)) {
i++;
}
while (cmp(pivot, (char*)a + j*item)) {
j--;
}
if (i <= j) {
if (cmp((char*)a + j*item, (char*)a + i*item)) {
memcpy(tmp, (char*)a + i*item, item);
memcpy((char*)a + i*item, (char*)a + j*item, item);
memcpy((char*)a + j*item, tmp, item);
}
i++;
if (j > 0) {
j--;
}
}
} while (i <= j);
if (i < high) {
push(lows, i);
push(highs, high);
}
if (j > low) {
push(lows, low);
push(highs, j);
}
}
freeStack(&lows);
freeStack(&highs);
free(tmp);
} Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно. // qsort (0, n-1);
Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. Для примера это, может, и нормально, но при решении, например, олимпиадных задач, хитрое жюри может специально подобрать такие тесты, чтобы на них это решение работало слишком долго и не проходило в лимит. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента - один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью. Писáл сам, изредка поглядывая на Википедию . Пользуясь случаем, передаю спасибо замечательным преподавателям и студентам ПетрГУ, научившим меня множеству полезных вещей, в том числе и этому алгоритму! Теги:
Qsort, быстрая сортировка, алгоритмы сортировки, алгоритмы, C Обновлено: 18.03.2019
Быстрая сортировка
(quick sort
), или сортировка Хоара - один из самых быстрых алгоритмов сортирования данных. Алгоритм Хоара - это модифицированный вариант метода прямого обмена. Другие популярные варианты этого метода - сортировка пузырьком
и шейкерная сортировка
, в отличии от быстрой сортировки, не очень эффективны. Идея алгоритма следующая: Поскольку метод быстрой сортировки разделяет массив на части, он относиться к группе алгоритмов разделяй и властвуй
. Метод Partition возвращает индекс опорного елемента, который делит массив на элементы меньше опорного слева, и элементы больше опорного справа. В самом методе в качестве опорного выбирается последний элемент, а обход осуществляется от начала массива. Быстрая сортировка (англ. quicksort
), часто называемая qsort
(по имени в стандартной библиотеке языка Си) - широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
Реализация алгоритма на различных языках программирования:
Работает для произвольного массива из n целых чисел. Int n, a[n]; //n - количество элементов
void qs(int* s_arr, int first, int last)
{
int i = first, j = last, x = s_arr[(first + last) / 2];
do {
while (s_arr[i] < x) i++;
while (s_arr[j] > x) j--;
if(i <= j) {
if (s_arr[i] > s_arr[j]) swap(&s_arr[i], &s_arr[j]);
i++;
j--;
}
} while (i <= j);
if (i < last)
qs(s_arr, i, last);
if (first < j)
qs(s_arr, first, j);
} Исходный вызов функции qs для массива из n элементов будет иметь следующий вид. Int partition (int array, int start, int end)
{
int marker = start;
for (int i = start; i <= end; i++)
{
if (array[i] <= array)
{
int temp = array; // swap
array = array[i];
array[i] = temp;
marker += 1;
}
}
return marker - 1;
}
void quicksort (int array, int start, int end)
{
if (start >= end)
{
return;
}
int pivot = partition (array, start, end);
quicksort (array, start, pivot-1);
quicksort (array, pivot+1, end);
} Int partition Using System;
using System.Collections.Generic;
using System.Linq;
static public class Qsort
{
public static IEnumerable Быстрая сортировка на основе библиотеки STL.
#include <=N;i=i+1) {
A[i]=N-i;
System.out.print(A[i]+" ");
}
System.out.println("\nBefore qSort\n");
// перемешивание массива
Random r = new Random(); //инициализация от таймера
int yd,xs;
for (int i=0;i<=N;i=i+1) {
yd=A[i];
xs=r.nextInt(N+1);
A[i]=A;
A=yd;
}
for (int i=0;i<=N;i=i+1)
System.out.print(A[i]+" ");
System.out.println("\nAfter randomization\n");
long start, end;
int low=0;
int high=N;
start=System.nanoTime(); // получить начальное время
qSort(A,low,high);
end=System.nanoTime(); // получить конечное время
for (int i=0;i<=N;i++)
System.out.print(A[i]+" ");
System.out.println("\nAfter qSort");
System.out.println("\nTime of running: "+(end-start)+"nanosec");
}
//описание функции qSort
public static void qSort(int A, int low, int high) {
int i = low;
int j = high;
int x = A[(low+high)/2];
do {
while(A[i] < x) ++i;
while(A[j] > x) --j;
if(i <= j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
i ++ ; j --;
}
} while(i <= j);
//рекурсивные вызовы функции qSort
if(low < j) qSort(A, low, j);
if(i < high) qSort(A, i, high);
}
} Import java.util.Random;
public class QuickSort {
public static void main(String args) {
int N=10;
int A;
A = new int;
// заполнение массива
for (int i=0;i<=N;i=i+1) {
A[i]=N-i;
System.out.print(A[i]+" ");
}
System.out.println("\nBefore qSort\n");
// перемешивание массива
Random r = new Random(); //инициализация от таймера
int yd,xs;
for (int i=0;i<=N;i=i+1) {
yd=A[i];
xs=r.nextInt(N+1);
A[i]=A;
A=yd;
}
for (int i=0;i<=N;i=i+1)
System.out.print(A[i]+" ");
System.out.println("\nAfter randomization\n");
long start, end;
int low=0;
int high=N;
start=System.nanoTime(); // получить начальное время
qSort(A,low,high);
end=System.nanoTime(); // получить конечное время
for (int i=0;i<=N;i++)
System.out.print(A[i]+" ");
System.out.println("\nAfter qSort");
System.out.println("\nTime of running: "+(end-start)+"nanosec");
}
//описание функции qSort
public static void qSort(int A, int low, int high) {
int i = low;
int j = high;
int x = A[(low+high)/2];
do {
while(A[i] < x) ++i;
while(A[j] > x) --j;
if(i <= j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
i ++ ; j --;
}
} while(i <= j);
//рекурсивные вызовы функции qSort
if(low < j) qSort(A, low, j);
if(i < high) qSort(A, i, high);
}
} С использованием генераторов: Def qsort(L):
if L: return qsort( if x Математическая версия: Def qsort(L):
if L: return qsort(filter(lambda x: x < L, L)) + L + qsort(filter(lambda x: x >= L, L))
return Qsort =
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) Математическая версия - с использованием генераторов: Qsort =
qsort (x:xs) = qsort ++ [x] ++ qsort В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" - она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует "императивные" макросы Common Lisp"а. (defun quickSort (array l r)
(let ((i l)
(j r)
(p (svref array (round (+ l r) 2))))
(while (<= i j)
(while (< (svref array i) p) (incf i))
(while (> (svref array j) p) (decf j))
(when (<= i j)
(rotatef (svref array i) (svref array j))
(incf i)
(decf j)))
(if (>= (- j l) 1) (quickSort array l j))
(if (>= (- r i) 1) (quickSort array i r)))
array) В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его - зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве - он проще и быстрее, хотя, теоретически, может быть хуже. Внутреннее условие, помеченное комментарием «это условие можно убрать» - необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии - будут обменены местами. Что займёт больше времени - проверки или лишние перестановки, - зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым. Const max=20; { можно и больше... }
type
list = array of integer;
procedure quicksort(var a: list; Lo,Hi: integer);
procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l; j:=r; x:=a; { x:= a[(r+l) div 2]; - для выбора среднего элемента }
repeat
while a[i] Устойчивый вариант (требует дополнительно O(n)памяти) Const max=20; { можно и больше… }
type
list = array of integer;
procedure quicksort(var a: list; Lo,Hi: integer);
procedure sort(l,r: integer);
var
i,j,x,xval,y: integer;
begin
i:=l; j:=r; x:=random(r-l+1)+l; xval:=a[x]; xvaln:=num[x]{ x:=(r+l) div 2; - для выбора среднего элемента }
repeat
while (a[i] Быстрая сортировка, нерекурсивный вариант
Нерекурсивная реализация быстрой сортировки через стек. Функции compare и change реализуются в зависимости от типа данных. Procedure quickSort(var X: itemArray; n: integer);
type
p_node = ^node;
node = record
node: integer;
next: p_node
end;
var
l,r,i,j: integer;
stack: p_node;
temp: item;
procedure push(i: integer);
var
temp: p_node;
begin
new(temp);
temp^.node:=i;
temp^.next:=stack;
stack:=temp
end;
function pop: integer;
var
temp: p_node;
begin
if stack=nil then
pop:=0
else
begin
temp:=stack;
pop:=stack^.node;
stack:=stack^.next;
dispose(temp)
end
end;
begin
stack:=nil;
push(n-1);
push(0);
repeat
l:=pop;
r:=pop;
if r-l=1 then
begin
if compare(X[l],X[r]) then
change(X[l],X[r])
end
else
begin
temp:=x[(l+r) div 2]; {random(r-l+1)+l}
i:=l;
j:=r;
repeat
while compare(temp,X[i]) do i:=i+1;
while compare(X[j],temp) do j:=j-1;
if i<=j then
begin
change(X[i],X[j]);
i:=i+1;
j:=j-1
end;
until i>j;
if l This example demonstrates the use of an arbitrary predicate in a functional language. Fun quicksort lt lst =
let val rec sort =
fn =>
| (x::xs) =>
let
val (left,right) = List.partition (fn y => lt (y, x)) xs
in sort left @ x:: sort right
end
in sort lst
end
@out=(5,2,7,9,2,5,67,1,5,7,-8,5,0);
sub sortQ{
my($s, $e) = @_;
my $m = $s - 1;
for($s..$e - 1){
if($out[$_] lt $out[$e]){
++$m;
($out[$m], $out[$_]) = ($out[$_], $out[$m]);
}
}
++$m;
($out[$m], $out[$e]) = ($out[$e], $out[$m]);
sortQ($s, $m-1) if $s < $m-1;
sortQ($m+1, $e) if $m+1 < $e;
}
sortQ(0, $#out); Let rec quicksort = function
->
| h::t -> quicksort ([ for x in t when x<=h -> x])
@ [h] @ quicksort ([ for x in t when x>h -> x]);; Let rec qsort l=match l with
->
|a::b-> (qsort (List.filter ((>=) a) b) lt) @ [a] @ (qsort (List.filter ((<) a) b));; Qsort() -> ;
qsort() -> qsort() ++ [H] ++ qsort(). Array qsort(array)(array _a)
{
alias typeof(array.init) _type;
array filter(bool delegate(_type) dg, array a){
array buffer = null;
foreach(value; a) {
if(dg(value)){
buffer ~= value;
}
}
return buffer;
}
if(_a.length <= 1) {
return _a;
}
else {
return qsort(filter((_type e){ return _a >= e; }, _a)) ~ _a ~
qsort(filter((_type e){ return _a < e; }, _a));
}
} Более короткий вариант с использованием стандартной библиотеки Phobos: Import std.algorithm;
T _qsort3(T)(T a) {
if(a.length <= 1)
return a;
else
return _qsort3(a.filter!(e => a >= e).array) ~ a ~
_qsort3(a.filter!(e => a < e).array);
} Def qsort](list: List[A]): List[A] = list match
{
case head::tail =>
{
qsort(tail filter(head>=)) ::: head:: qsort(tail filter(head<))
}
case _ => list;
} Еще вариант: Def sort(xs: Array): Array = {
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(sort(xs filter (pivot >)), xs filter (pivot ==), sort(xs filter (pivot <)))
}
} Ленивая реализация: (defn qsort []
(letfn [(f [g] (qsort (filter #(g % x) xs)))]
(when x (lazy-cat (f <) [x] (f >=))))) (define filter
{(A --> boolean) --> (list A) --> (list A)}
_ ->
T? -> (append [A] (filter T? B)) where (T? A)
T? [_|B] -> (filter T? B))
(define q-sort
{(list number) --> (list number)}
->
-> (append (q-sort (filter (> A) ))
[A]
(q-sort (filter (< A) )))) Судя по тестам, сортировка пузырьком 5000 занимает в 8 с половиной раз больше времени, чем qSort"ом Sub Swap(ByRef Val1, ByRef Val2)
Dim Proc
Proc = Val1
Val1 = Val2
Val2 = Proc
End Sub
Function partition(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer, ByRef pivot As Integer)
Dim i
Dim piv
Dim store
piv = a(pivot)
Swap(a(right - 1), a(pivot))
store = left
For i = left To right - 2
If a(i) <= piv Then
Swap(a(store), a(i))
store = store + 1
End If
Next
Swap(a(right - 1), a(store))
Return store
End Function
Function getpivot(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
Return New System.Random().Next(left, right - 1)
End Function
Sub quicksort(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
Dim pivot As Integer
If right - left > 1 Then
pivot = getpivot(a, left, right)
pivot = partition(a, left, right, pivot)
quicksort(a, left, pivot)
quicksort(a, pivot + 1, right)
End If
End Sub
Sub qSort(ByVal a() As Integer)
Dim i
Dim ii
For i = 0 To a.Length() - 1
ii = New System.Random().Next(0, a.Length() - 1)
If i <> ii Then
Swap(a(i), a(ii))
End If
Next
quicksort(a, 0, a.Length())
End Sub Вызов функции: QSort(имя сортируемого массива)
Function
quicksort (&
$array
,
$l
=
0
,
$r
=
0
)
{
if($r === 0) $r = count($array)-1;
$i = $l;
$j = $r;
$x = $array[($l + $r) / 2];
do {
while ($array[$i] < $x) $i++;
while ($array[$j] > $x) $j--;
if ($i <= $j) {
if ($array[$i] > $array[$j])
list($array[$i], $array[$j]) = array($array[$j], $array[$i]);
$i++;
$j--;
}
} while ($i <= $j);
if ($i < $r) quicksort ($array, $i, $r);
if ($j > $l) quicksort ($array, $l, $j);
} Здесь приведен алгоритм сортировки на примере объекта типа «СписокЗначений», но его можно модифицировать для работы с любым объектом, для этого нужно изменить соответствующим образом код функций «СравнитьЗначения», «ПолучитьЗначение», «УстановитьЗначение». Функция СравнитьЗначения(Знач1, Знач2)
Если Знач1>Знач2 Тогда
Возврат 1;
КонецЕсли;
Если Знач1<Знач2 Тогда
Возврат -1;
КонецЕсли;
Возврат 0;
КонецФункции
Функция ПолучитьЗначение(Список, Номер)
Возврат Список.Получить(Номер-1).Значение;
КонецФункции
Процедура УстановитьЗначение(Список, Номер, Значение)
Список[Номер-1].Значение = Значение;
КонецПроцедуры
Процедура qs_0(s_arr, first, last)
i = first;
j = last;
x = ПолучитьЗначение(s_arr, Окр((first + last) / 2, 0));
Пока i <= j Цикл
Пока СравнитьЗначения(ПолучитьЗначение(s_arr, i), x)=-1 Цикл
i=i+1;
КонецЦикла;
Пока СравнитьЗначения(ПолучитьЗначение(s_arr, j), x)=1 Цикл
j=j-1;
КонецЦикла;
Если i <= j Тогда
Если i < j Тогда
к=ПолучитьЗначение(s_arr, i);
УстановитьЗначение(s_arr, i, ПолучитьЗначение(s_arr, j));
УстановитьЗначение(s_arr, j, к);
КонецЕсли;
i=i+1;
j=j-1;
КонецЕсли;
КонецЦикла;
Если i < last Тогда
qs_0(s_arr, i, last);
КонецЕсли;
Если first < j Тогда
qs_0(s_arr, first,j);
КонецЕсли;
КонецПроцедуры
Процедура Сортировать(Список, Размер="", Первый="", Последний="")
Если Не ЗначениеЗаполнено(Первый) Тогда
Первый=1;
КонецЕсли;
Если НЕ ЗначениеЗаполнено(Последний) Тогда
Последний=Размер;
КонецЕсли;
qs_0(Список, Первый, Последний);
КонецПроцедуры DEF FN QSORT(LOW,HIGH)
LOCAL I,J,X,TEMP
J=HIGH
X=Y[(LOW+HIGH)/2]
DO
WHILE Y[I] Пример вызова функции FN QSORT(LOW,HIGH), входные и выходные данные в массиве DIM Y LOW=N1
HIGH=N2
F=FN QSORT(LOW,HIGH)
Стоит отметить, что быстрая сортировка может оказаться малоэффективной на массивах, состоящих из небольшого числа элементов, поэтому при работе с ними разумнее отказаться от данного метода. В целом алгоритм неустойчив, а также использование рекурсии в неверно составленном коде может привести к переполнению стека. Но, несмотря на эти и некоторые другие минусы, быстрая сортировка все же является одним из самых эффективных и часто используемых методов.
При написании статьи были использованы открытые источники сети интернет:
1. Небольшие Подфайлы.
2. Деление по Медиане из Трех
3. Нерекурсивная реализация.
Слияние
Прямое слияние. Алгоритм Боуза - Нельсона
Естественное (Неймановское) слияние.
Рекурсивное решение
Итеративное решение
Итак, быстрая сортировка, или, по названию функции в Си, Qsort - это алгоритм сортировки, сложность которого в среднем
составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.Алгоритм
Что ж, выглядит не так уж сложно. Реализуем на Си? Нет проблем! void
qsort (int
b, int
e)
{
int
l = b, r = e;
int
piv = arr[(l + r) / 2]; // Опорным элементом для примера возьмём средний
while
(l <= r)
{
while
(arr[l] < piv)
l++;
while
(arr[r] > piv)
r--;
if
(l <= r)
swap (arr, arr);
}
if
(b < r)
qsort (b, r);
if
(e > l)
qsort (l, e);
} /* ----- end of function qsort ----- */
* This source code was highlighted with Source Code Highlighter
.
Принцип работы алгоритма быстрой сортировки
Реализация быстрой сортировки
using System;
class Program
{
//метод для обмена элементов массива
static void Swap(ref int x, ref int y)
{
var t = x;
x = y;
y = t;
}
//метод возвращающий индекс опорного элемента
static int Partition(int array, int minIndex, int maxIndex)
{
var pivot = minIndex - 1;
for (var i = minIndex; i < maxIndex; i++)
{
if (array[i] < array)
{
pivot++;
Swap(ref array, ref array[i]);
}
}
pivot++;
Swap(ref array, ref array);
return pivot;
}
//быстрая сортировка
static int QuickSort(int array, int minIndex, int maxIndex)
{
if (minIndex >= maxIndex)
{
return array;
}
var pivotIndex = Partition(array, minIndex, maxIndex);
QuickSort(array, minIndex, pivotIndex - 1);
QuickSort(array, pivotIndex + 1, maxIndex);
return array;
}
static int QuickSort(int array)
{
return QuickSort(array, 0, array.Length - 1);
}
static void Main(string args)
{
Console.Write("N = ");
var len = Convert.ToInt32(Console.ReadLine());
var a = new int;
for (var i = 0; i < a.Length; ++i)
{
Console.Write("a[{0}] = ", i);
a[i] = Convert.ToInt32(Console.ReadLine());
}
Console.WriteLine("Упорядоченный массив: {0}", string.Join(", ", QuickSort(a)));
Console.ReadLine();
}
}
C
Java/C#
C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable
C# с использованием лямбда-выражений
C++
Java
import java.util.Comparator;
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private void swap(Object array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private int partition(Object array, int begin, int end, Comparator cmp) {
int index = begin + RND.nextInt(end - begin + 1);
Object pivot = array;
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private void qsort(Object array, int begin, int end, Comparator cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public void sort(Object array, Comparator cmp) {
qsort(array, 0, array.length - 1, cmp);
}
Java, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива)
JavaScript
Python
Joy
DEFINE sort ==
split]
[ dip cons concat] binrec .
PHP
function qsort($s) {
for($i=0, $x=$y=array(); $iCommon Lisp
Pascal
Prolog
split(H, , , Z) :-
order(A, H), split(H, X, Y, Z).
split(H, , Y, ) :-
not(order(A, H)), split(H, X, Y, Z).
split(_, , , ).
quicksort(, X, X).
quicksort(, S, X) :-
split(H, T, A, B),
quicksort(A, S, ),
quicksort(B, Y, X).
Ruby
def sort(array)
return if array.empty?
left, right = array.partition { |y| y <= array.first }
sort(left) + [ array.first ] + sort(right)
end
SML
JavaScript
function QuickSort(A, p, r)
{
if(pPerl
F#
OCaml
Erlang
D
Scala
Clojure
Shen/Qi II
VB.NET
PHP
Встроенный язык 1С 8.*
Turbo Basic 1.1
