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
TCL
# Функция выбирает подсписок из списка используя условие condition
proc lfind {data arg condition} {
set foo
foreach item $data {
set $arg $item
if {} {lappend foo $item}
}
return $foo
}
# Сама сотрировка
proc QSort data {
set result {}
if { != 0} {
set check
set result [
concat \
] \
\
]]
}
return $result
}
Perl
@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);
F#
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]);;
OCaml
Let rec qsort l=match l with
->
|a::b-> (qsort (List.filter ((>=) a) b) lt) @ [a] @ (qsort (List.filter ((<) a) b));;
Erlang
Qsort() -> ;
qsort() -> qsort() ++ [H] ++ qsort().
D
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);
}
Scala
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 <)))
}
}
Clojure
Ленивая реализация:
(defn qsort []
(letfn [(f [g] (qsort (filter #(g % x) xs)))]
(when x (lazy-cat (f <) [x] (f >=)))))
Shen/Qi II
(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) ))))
VB.NET
Судя по тестам, сортировка пузырьком 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(имя сортируемого массива)
PHP
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С 8.*
Здесь приведен алгоритм сортировки на примере объекта типа «СписокЗначений», но его можно модифицировать для работы с любым объектом, для этого нужно изменить соответствующим образом код функций «СравнитьЗначения», «ПолучитьЗначение», «УстановитьЗначение».
Функция СравнитьЗначения(Знач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(Список, Первый, Последний);
КонецПроцедуры
Turbo Basic 1.1
DEF FN QSORT(LOW,HIGH)
LOCAL I,J,X,TEMP
J=HIGH
X=Y[(LOW+HIGH)/2]
DO
WHILE Y[I]X:J=J-1:WEND
IF I<=J THEN
TEMP=Y[I]
Y[I]=Y[J]
Y[J]=TEMP
I=I+1
J=J-1
END IF
LOOP WHILE I<=J
IF LOW
Пример вызова функции FN QSORT(LOW,HIGH), входные и выходные данные в массиве DIM Y
LOW=N1
HIGH=N2
F=FN QSORT(LOW,HIGH)
Стоит отметить, что быстрая сортировка может оказаться малоэффективной на массивах, состоящих из небольшого числа элементов, поэтому при работе с ними разумнее отказаться от данного метода. В целом алгоритм неустойчив, а также использование рекурсии в неверно составленном коде может привести к переполнению стека. Но, несмотря на эти и некоторые другие минусы, быстрая сортировка все же является одним из самых эффективных и часто используемых методов.
При написании статьи были использованы открытые источники сети интернет:
Представляет собой усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал его быстрой сортировкой.
Для достижения наибольшей эффективности желательно производить обмен элементов на больших расстояниях. В массиве выбирается некоторый элемент, называемый разрешающим
. Затем он помещается в то место массива, где ему полагается быть после упорядочивания всех элементов. В процессе отыскания подходящего места для разрешающего элемента производятся перестановки элементов так, что слева от них находятся элементы, меньшие разрешающего, и справа - большие (предполагается, что массив сортируется по возрастанию).
Тем самым массив разбивается на две части:
- не отсортированные элементы слева от разрешающего элемента;
- не отсортированные элементы справа от разрешающего элемента.
Чтобы отсортировать эти два меньших подмассива, алгоритм рекурсивно вызывает сам себя.
Если требуется сортировать больше одного элемента, то нужно
- выбрать в массиве разрешающий элемент;
- переупорядочить массив, помещая элемент на его окончательное место;
- отсортировать рекурсивно элементы слева от разрешающего;
- отсортировать рекурсивно элементы справа от разрешающего.
Ключевым элементом быстрой сортировки является алгоритм переупорядочения
.
Рассмотрим сортировку на примере массива:
10, 4, 2, 14, 67, 2, 11, 33, 1, 15.
Для реализации алгоритма переупорядочения используем указатель left
на крайний левый элемент массива. Указатель движется вправо, пока элементы, на которые он показывает, остаются меньше разрешающего. Указатель right
поставим на крайний правый элемент массива, и он движется влево, пока элементы, на которые он показывает, остаются больше разрешающего.
Пусть крайний левый элемент - разрешающий pivot
. Установим указатель left
на следующий за ним элемент; right
- на последний. Алгоритм должен определить правильное положение элемента 10 и по ходу дела поменять местами неправильно расположенные элементы.
Движение указателей останавливается, как только встречаются элементы, порядок расположения которых относительно разрешающего элемента неправильный.
Указатель left
перемещается до тех пор, пока не покажет элемент больше 10; right
движется, пока не покажет элемент меньше 10.
![](https://i0.wp.com/prog-cpp.ru/wp-content/uploads/2014/05/fastsort2.png)
Эти элементы меняются местами и движение указателей возобновляется.
![](https://i0.wp.com/prog-cpp.ru/wp-content/uploads/2014/05/fastsort3.png)
Процесс продолжается до тех пор, пока right
не окажется слева от left
.
![](https://i1.wp.com/prog-cpp.ru/wp-content/uploads/2014/05/fastsort4.png)
Тем самым будет определено правильное место разрешающего элемента.
Осуществляется перестановка разрешающего элемента с элементом, на который указывает right
.
![](https://i0.wp.com/prog-cpp.ru/wp-content/uploads/2014/05/fastsort5.png)
Разрешающий элемент находится в нужном месте: элементы слева от него имеют меньшие значения; справа - большие. Алгоритм рекурсивно вызывается для сортировки подмассивов слева от разрешающего и справа от него.
Реализация алгоритма быстрой сортировки на Си
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include
#include
#define
SIZE 20
// Функция быстрой сортировки
void
quickSort(int
*numbers, int
left, int
right)
{
int
pivot; // разрешающий элемент
int
l_hold = left; //левая граница
int
r_hold = right; // правая граница
pivot = numbers;
while
(left < right) // пока границы не сомкнутся
{
while
((numbers >= pivot) && (left < right))
right--; // сдвигаем правую границу пока элемент больше
if
(left != right)
{
numbers = numbers; // перемещаем элемент на место разрешающего
left++; // сдвигаем левую границу вправо
}
while
((numbers <= pivot) && (left < right))
left++; // сдвигаем левую границу пока элемент меньше
if
(left != right) // если границы не сомкнулись
{
numbers = numbers; // перемещаем элемент на место
right--; // сдвигаем правую границу вправо
}
}
numbers = pivot; // ставим разрешающий элемент на место
pivot = left;
left = l_hold;
right = r_hold;
if
(left < pivot) // Рекурсивно вызываем сортировку для левой и правой части массива
quickSort(numbers, left, pivot - 1);
if
(right > pivot)
quickSort(numbers, pivot + 1, right);
}
int
main()
{
int
a;
// Заполнение массива случайными числами
for
(int
i = 0; i a[i] = rand() % 201 - 100;
// Вывод элементов массива до сортировки
for
(int
i = 0; i printf("%4d "
, a[i]);
printf("\n"
);
quickSort(a, 0, SIZE-1); // вызов функции сортировки
// Вывод элементов массива после сортировки
for
(int
i = 0; i printf("%4d "
, a[i]);
printf("\n"
);
getchar();
return
0;
}
Результат выполнения
Выбирая алгоритм сортировки для практических целей, программист, вполне вероятно, остановиться на методе, называемом «Быстрая сортировка» (также «qsort» от англ. quick sort). Его разработал в 1960 году английский ученый Чарльз Хоар, занимавшийся тогда в МГУ машинным переводом. Алгоритм, по принципу функционирования, входит в класс обменных сортировок (сортировка перемешиванием, пузырьковая сортировка и др.), выделяясь при этом высокой скоростью работы.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному.
Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
- разбиение массива относительно опорного элемента;
- рекурсивная сортировка каждой части массива.
Разбиение массива.
Еще раз об опорном элементе. Его выбор не влияет на результат, и поэтому может пасть на произвольный элемент. Тем не менее, как было замечено выше, наибольшая эффективность алгоритма достигается при выборе опорного элемента, делящего последовательность на равные или примерно равные части. Но, как правило, из-за нехватки информации не представляется возможности наверняка определить такой элемент, поэтому зачастую приходиться выбирать опорный элемент случайным образом.
В следующих пяти пунктах описана общая схема разбиения массива (сортировка по возрастанию):
- вводятся указатели first
и last
для обозначения начального и конечного элементов последовательности, а также опорный элемент mid
;
- вычисляется значение опорного элемента (first
+last
)/2, и заноситься в переменную mid
;
- указатель first
смещается с шагом в 1 элемент к концу массива до тех пор, пока Mas
[first
]>mid
. А указатель last
смещается от конца массива к его началу, пока Mas
[last
]<mid
;
- каждые два найденных элемента меняются местами;
- пункты 3 и 4 выполняются до тех пор, пока first
После разбиения последовательности следует проверить условие на необходимость дальнейшего продолжения сортировки его частей. Этот этап будет рассмотрен позже, а сейчас на конкретном примере выполним разбиение массива.
Имеется массив целых чисел Mas
, состоящий из 8 элементов (рис. 5.5): Mas
. Начальным значением first
будет 1, а last
– 8. Пройденная часть закрашивается голубым цветом.
В качестве опорного элемента возьмем элемент со значением 5, и индексом 4. Его мы вычислили, используя выражение (first
+last
)/2, отбросив дробную часть. Теперь mid
=5.
Первый элемент левой части сравнивается с mid
. Mas
>mid
, следовательно first
остается равным 1. Далее, элементы правой части сравниваются с mid
. Проверяется элемент с индексом 8 и значением 8. Mas
>mid
, следовательно last
смещается на одну позицию влево. Mas
<mid
, следовательно last
остается равным 7. На данный момент first
=1, а last
=7. Первый и седьмой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении.
Алгоритм снова переходит к сравнению элементов. Второй элемент сравнивается с опорным: Mas
>mid, следовательно first
остается равным 2. Далее, элементы правой части сравниваются с mid
. Проверяется элемент с индексом 6 и значением 1: Mas
<mid
, следовательно last
не изменяет своей позиции. На данный момент first
=2, а last
=6. Второй и шестой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении.
Алгоритм снова переходит к сравнению элементов. Третий элемент сравнивается с опорным: Mas
<mid
, следовательно first
смещается на одну позицию вправо. Далее, элементы правой части сравниваются с mid
. Проверяется элемент с индексом 5 и значением 9: Mas
>mid
, следовательно last
смещается на одну позицию влево. Теперь first
=last
=4, а значит, условие first
<last
не выполняется, этап разбиения завершается.
На этом этап разбиения закончен. Массив разделен на две части относительно опорного элемента. Осталось произвести рекурсивное упорядочивание его частей.
Рекурсивное доупорядочивание
Если в какой-то из получившихся в результате разбиения массива частей находиться больше одного элемента, то следует произвести рекурсивное упорядочивание этой части, то есть выполнить над ней операцию разбиения, описанную выше. Для проверки условия «количество элементов > 1», нужно действовать примерно по следующей схеме:
Имеется массив Mas
[L
..R
], где L
и R
– индексы крайних элементов этого массива. По окончанию разбиения, указатели first
и last
оказались примерно в середине последовательности, тем самым образуя два отрезка: левый от L
до last
и правый от first
до R
. Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L
<last
. Для правой части условие аналогично: first
<R
.
Реализации алгоритма быстрой сортировки:
Код программы на C++:
#include "stdafx.h"
#include
#include
using namespace std;
const int n=7;
int first, last;
//функция сортировки
void quicksort(int *mas, int first, int last)
{
int mid, count;
int f=first, l=last;
mid=mas[(f+l) / 2]; //вычисление опорного элемента
do
{
while (mas[f]mid) l--;
if (f<=l) //перестановка элементов
{
count=mas[f];
mas[f]=mas[l];
mas[l]=count;
f++;
l--;
}
} while (f>void");
}
|
#include "stdafx.h"
#include
#include
using
namespace
std
;
const
int
n
=
7
;
int
first
,
last
;
//функция сортировки
void
quicksort
(int
*
mas
,
int
first
,
int
last
)
int
mid
,
count
;
int
f
=
first
,
l
=
last
;
mid
=
mas
[
(f
+
l
)
/
2
]
;
//вычисление опорного элемента
while
(mas
[
f
]
<
mid
)
f
++
;
while
(mas
[
l
]
>
mid
)
l
--
;
if
(f
<=
l
)
//перестановка элементов
count
=
mas
[
f
]
;
mas
[
f
]
=
mas
[
l
]
;
mas
[
l
]
=
count
;
f
++
;
l
--
;
}
while
(f
<
l
)
;
if
(first
<
l
)
quicksort
(mas
,
first
,
l
)
;
if
(f
<
last
)
quicksort
(mas
,
f
,
last
)
;
//главная функция
void
main
()
setlocale
(LC_ALL
,
"Rus"
)
;
int
*
A
=
new
int
[
n
]
;
srand
(time
(NULL
)
)
;
cout
<<
"Исходный массив: "
;
for
(int
i
=
0
;
i
<
n
;
i
++
)
A
[
i
]
=
rand
()
%
10
;
cout
<<
A
[
i
]
<<
" "
;
first
=
0
;
last
=
n
-
1
;
quicksort
(A
,
first
,
last
)
;
cout
<<
endl
<<
"Результирующий массив: "
;
for
(int
i
=
0
;
i
<
n
;
i
++
)
cout
<<
A
[
i
]
<<
" "
;
delete
A
;
system
("pause>>void"
)
;
|
Код программы на Pascal:
Delphi/Pascal
program qsort;
uses crt;
const n=7;
var A: array of integer;
first, last, i: integer;
{процедура сортировки}
procedure quicksort(var mas: array of integer; first, last: integer);
var f, l, mid, count: integer;
begin
f:=first;
l:=last;
mid:=mas[(f+l) div 2]; {вычисление опорного элемента}
repeat
while mas[f]mid do dec(l);
if f<=l then {перестановка элементов}
begin
count:=mas[f];
mas[f]:=mas[l];
mas[l]:=count;
inc(f);
dec(l);
end;
until f>l;
if first
|
program
qsort
;
uses
crt
;
const
n
=
7
;
var
A
:
array
[
1..n
]
of
integer
;
first
,
last
,
i
:
integer
;
{
процедурасортировки}
procedure
quicksort
(var
mas
:
array
[
1..n
]
of
integer
;
first
,
last
:
integer
)
;
var
f
,
l
,
mid
,
count
:
integer
;
begin
f
:=
first
;
l
:=
last
;
mid
:=
mas
[
(f
+
l
)
div
2
]
;
{
вычислениеопорногоэлемента}
repeat
while
mas
[
f
]
<
mid
do
inc
(f
)
;
while
mas
[
l
]
>
mid
do
dec
(l
)
;
|
Краткое описание алгоритма
- выбрать элемент, называемый опорным.
- сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три - «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
- повторить рекурсивно для «меньших» и «больших».
Примечание: на практике обычно разделяют сортируемое множество не на три, а на две части: например, «меньшие опорного» и «равные и большие». Такой подход в общем случае оказывается эффективнее, так как для осуществления такого разделения достаточно одного прохода по сортируемому множеству и однократного обмена лишь некоторых выбранных элементов.
Алгоритм
Быстрая сортировка использует стратегию «разделяй и властвуй ». Шаги алгоритма таковы:
- Выбираем в массиве некоторый элемент, который будем называть опорным элементом
. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана , но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
- Операция разделения
массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного - справа от него. Обычный алгоритм операции:
- Два индекса - l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
- Вычисляется индекс опорного элемента m.
- Индекс l последовательно увеличивается до тех пор, пока l-й элемент не превысит опорный.
- Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
- Если r = l - найдена середина массива - операция разделения закончена, оба индекса указывают на опорный элемент.
- Если l < r - найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
- Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
- Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.
Интересно, что Хоар разработал этот метод применительно к машинному переводу : дело в том, что в то время словарь хранился на магнитной ленте , и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе , где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника (говорят, этот алгоритм был подслушан им у русских студентов).
//алгоритм на языке java
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)
;
if
(low <
j)
qSort(A, low, j)
;
if
(i <
high)
qSort(A, i, high)
;
}
|
//алгоритм на языке pascal
procedure
qSort(var
ar:
array
of
real
;
low,
high:
integer
)
;
var
i,
j:
integer
;
m,
wsp:
real
;
begin
i:
=
low;
j:
=
high;
m:
=
ar[
(i+
j)
div
2
]
;
repeat
while
(ar[
i]
m)
do
j:
=
j-
1
;
if
(i<=
j)
then
begin
wsp:
=
ar[
i]
;
ar[
i]
:
=
ar[
j]
;
ar[
j]
:
=
wsp;
i:
=
i+
1
;
j:
=
j-
1
;
end
;
until
(i > j)
;
if
(low
|
//алгоритм на языке Visual Basic
//при первом вызове 2-ой аргумент должен быть равен 1
//3-ий аргумент должен быть равен числу элементов массива
Sub qSort(ByVal ar()
As double,
ByVal low As Integer
,
ByVal high As Integer
)
Dim i,
j As Integer
Dim m,
wsp As double
i =
low
j =
high
m =
ar((i +
j)
\ 2
)
Do
Until
i > j
Do
While
ar(i)
< m
i +=
1
Loop
Do
While
ar(j)
> m
j -=
1
Loop
If
(i <=
j)
Then
wsp =
ar(i)
ar(i)
=
ar(j)
ar(j)
=
wsp
i +=
1
j -=
1
End
If
Loop
If
(low < j)
Then
qSort(ar,
low,
j)
If
(i < high)
Then
qSort(ar,
i,
high)
End
Sub
|
Оценка эффективности
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка » и «Шейкерная сортировка »), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод.
- Лучший случай.
Для этого алгоритма самый лучший случай - если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения C N = 2C N/2 +N, что в явном выражении дает примерно N lg N сравнений. Это дало бы наименьшее время сортировки.
- Среднее.
Даёт в среднем O(n
log n
) обменов при упорядочении n
элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
На практике (в случае, когда обмены являются более затратной операцией, чем сравнения) быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n
lg n
), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2C N/2 покрывает расходы по сортировке двух полученных подмассивов; N - это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно C N = N lg N.
- Худший случай.
Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
Худший случай даёт O(n
²) обменов. Но количество обменов и, соответственно, время работы - это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.
Улучшения
- При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки - O(n
lg n
).
- Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов). Такой выбор также направлен против худшего случая.
- Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры . С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла - примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит log 2 n, а в худшем случае вырожденного разделения она вообще будет не более 2 - вся обработка пройдёт в цикле первого уровня рекурсии.
- Разбивать массив не на две, а на три части (см. Dual Pivot Quicksort).
Достоинства и недостатки
Достоинства:
Недостатки:
Примечания
Литература
- Ананий В. Левитин
Глава 4. Метод декомпозиции: Быстрая сортировка
// Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. - М
.: «Вильямс», 2006. - С. 174-179. - ISBN 5-8459-0987-2
- Кормен, Т. , Лейзерсон, Ч. , Ривест, Р. , Штайн, К.
Глава 7. Быстрая сортировка
// Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. - 2-е изд. - М
.: Вильямс, 2005. - С. 198-219. - ISBN 5-8459-0857-4
А
лгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за 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);
}