Метод быстрой сортировки. Рекурсивный алгоритм быстрой сортировки по возрастанию
O(log n ) вспомогательных (Седжвик 1978)
Быстрая сортировка , сортировка Хоара (англ. quicksort ), часто называемая qsort (по имени в стандартной библиотеке языка Си) - широко известный алгоритм сортировки , разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году .
algorithm quicksort(A, lo, hi) is if lo < hi then p:= partition(A, lo, hi) quicksort(A, lo, p – 1) quicksort(A, p + 1, hi) algorithm partition(A, lo, hi) is pivot:= A i:= lo - 1 for j:= lo to hi - 1 do if A[j] ≤ pivot then i:= i + 1 swap A[i] with A[j] swap A with A return i + 1Сортировка всего массива может быть выполнена с помощью выполнения quicksort(A, 1, length(A)) .
Разбиение Хоара
Данная схема использует два индекса (один в начале массива, другой в конце), которые приближаются друг к другу, пока не найдётся пара элементов, где один больше опорного и расположен перед ним, а второй меньше и расположен после. Эти элементы меняются местами. Обмен происходит до тех пор, пока индексы не пересекутся. Алгоритм возвращает последний индекс. . Схема Хоара эффективнее схемы Ломуто, так как происходит в среднем в три раза меньше обменов (swap) элементов, и разбиение эффективнее, даже когда все элементы равны. Подобно схеме Ломуто, данная схема также показывает эффективность в O (n 2) , когда входной массив уже отсортирован. Сортировка с использованием данной схемы нестабильна. Следует заметить, что конечная позиция опорного элемента необязательно совпадает с возвращённым индексом. Псевдокод :
algorithm quicksort(A, lo, hi) is if lo < hi then p:= partition(A, lo, hi) quicksort(A, lo, p) quicksort(A, p + 1, hi) algorithm partition(A, lo, hi) is pivot:= A i:= lo - 1 j:= hi + 1 loop forever do i:= i + 1 while A[i] < pivot do j:= j - 1 while A[j] > pivot if i >= j then return j swap A[i] with A[j]Повторяющиеся элементы
Для улучшения производительности при большом количестве одинаковых элементов в массиве может быть применена процедура разбиения массива на три группы: элементы меньшие опорного, равные ему и больше него. (Бентли и Макилрой называют это «толстым разбиением». Данное разбиение используется в функции qsort в седьмой версии Unix . ). Псевдокод:
algorithm quicksort(A, lo, hi) is if lo < hi then p:= pivot(A, lo, hi) left, right:= partition(A, p, lo, hi) // возвращается два значения quicksort(A, lo, left) quicksort(A, right, hi)Оценка сложности алгоритма
Ясно, что операция разделения массива на две части относительно опорного элемента занимает время . Поскольку все операции разделения, проделываемые на одной глубине рекурсии, обрабатывают разные части исходного массива, размер которого постоянен, суммарно на каждом уровне рекурсии потребуется также O (n) {\displaystyle O(n)} операций. Следовательно, общая сложность алгоритма определяется лишь количеством разделений, то есть глубиной рекурсии. Глубина рекурсии, в свою очередь, зависит от сочетания входных данных и способа определения опорного элемента.
Лучший случай. В наиболее сбалансированном варианте при каждой операции разделения массив делится на две одинаковые (плюс-минус один элемент) части, следовательно, максимальная глубина рекурсии, при которой размеры обрабатываемых подмассивов достигнут 1, составит log 2 n {\displaystyle \log _{2}n} . В результате количество сравнений, совершаемых быстрой сортировкой, было бы равно значению рекурсивного выражения C n = 2 ⋅ C n / 2 + n {\displaystyle C_{n}=2\cdot C_{n/2}+n} , что даёт общую сложность алгоритма O (n ⋅ log 2 n) {\displaystyle O(n\cdot \log _{2}n)} . Среднее. Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно. Прежде всего необходимо заметить, что в действительности необязательно, чтобы опорный элемент всякий раз делил массив на две одинаковых части. Например, если на каждом этапе будет происходить разделение на массивы длиной 75 % и 25 % от исходного, глубина рекурсии будет равна , а это по-прежнему даёт сложность . Вообще, при любом фиксированном соотношении между левой и правой частями разделения сложность алгоритма будет той же, только с разными константами. Будем считать «удачным» разделением такое, при котором опорный элемент окажется среди центральных 50 % элементов разделяемой части массива; ясно, вероятность удачи при случайном распределении элементов составляет 0,5. При удачном разделении размеры выделенных подмассивов составят не менее 25 % и не более 75 % от исходного. Поскольку каждый выделенный подмассив также будет иметь случайное распределение, все эти рассуждения применимы к любому этапу сортировки и любому исходному фрагменту массива. Удачное разделение даёт глубину рекурсии не более log 4 / 3 n {\displaystyle \log _{4/3}n} . Поскольку вероятность удачи равна 0,5, для получения k {\displaystyle k} удачных разделений в среднем потребуется 2 ⋅ k {\displaystyle 2\cdot k} рекурсивных вызовов, чтобы опорный элемент k раз оказался среди центральных 50 % массива. Применяя эти соображения, можно заключить, что в среднем глубина рекурсии не превысит 2 ⋅ log 4 / 3 n {\displaystyle 2\cdot \log _{4/3}n} , что равно O (log n) {\displaystyle O(\log n)} А поскольку на каждом уровне рекурсии по-прежнему выполняется не более O (n) {\displaystyle O(n)} операций, средняя сложность составит O (n log n) {\displaystyle O(n\log n)} . Худший случай. В самом несбалансированном варианте каждое разделение даёт два подмассива размерами 1 и , то есть при каждом рекурсивном вызове больший массив будет на 1 короче, чем в предыдущий раз. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых. При простейшем выборе опорного элемента - первого или последнего в массиве, - такой эффект даст уже отсортированный (в прямом или обратном порядке) массив, для среднего или любого другого фиксированного элемента «массив худшего случая» также может быть специально подобран. В этом случае потребуется n − 1 {\displaystyle n-1} операций разделения, а общее время работы составит ∑ i = 0 n (n − i) = O (n 2) {\displaystyle \textstyle \sum _{i=0}^{n}(n-i)=O(n^{2})} операций, то есть сортировка будет выполняться за квадратичное время. Но количество обменов и, соответственно, время работы - это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти (переполнению стека) во время работы программы.
Достоинства и недостатки
Достоинства:
Недостатки:
Улучшения
Улучшения алгоритма направлены, в основном, на устранение или смягчение вышеупомянутых недостатков, вследствие чего все их можно разделить на три группы: придание алгоритму устойчивости, устранение деградации производительности специальным выбором опорного элемента, и защита от переполнения стека вызовов из-за большой глубины рекурсии при неудачных входных данных.
- Проблема неустойчивости решается путём расширения ключа исходным индексом элемента в массиве. В случае равенства основных ключей сравнение производится по индексу, исключая, таким образом, возможность изменения взаимного положения равных элементов. Эта модификация не бесплатна - она требует дополнительно O(n) памяти и одного полного прохода по массиву для сохранения исходных индексов.
- Деградация по скорости в случае неудачного набора входных данных решается по двум разным направлениям: снижение вероятности возникновения худшего случая путём специального выбора опорного элемента и применение различных технических приёмов, обеспечивающих устойчивую работу на неудачных входных данных. Для первого направления:
- Выбор среднего элемента. Устраняет деградацию для предварительно отсортированных данных, но оставляет возможность случайного появления или намеренного подбора «плохого» массива.
- Выбор медианы из трёх элементов: первого, среднего и последнего. Снижает вероятность возникновения худшего случая, по сравнению с выбором среднего элемента.
- Случайный выбор. Вероятность случайного возникновения худшего случая становится исчезающе малой, а намеренный подбор - практически неосуществимым. Ожидаемое время выполнения алгоритма сортировки составляет O(n lg n ).
- Во избежание отказа программы из-за большой глубины рекурсии могут применяться следующие методы:
Быстрая сортировка (англ. quicksort ), часто называемая qsort (по имени в стандартной библиотеке языка Си) - широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
- разбиение массива относительно опорного элемента;
- рекурсивная сортировка каждой части массива.
Реализация алгоритма на различных языках программирования:
C
Работает для произвольного массива из 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 элементов будет иметь следующий вид.
Java/C#
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); }
C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable
Int partition
C# с использованием лямбда-выражений
Using System;
using System.Collections.Generic;
using System.Linq;
static public class Qsort
{
public static IEnumerable
C++
Быстрая сортировка на основе библиотеки STL.
#include
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, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива)
<=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); } }
JavaScript
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); } }
Python
С использованием генераторов:
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
Joy
DEFINE sort == split] [ dip cons concat] binrec .PHP
function qsort($s) { for($i=0, $x=$y=array(); $iQsort = qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Математическая версия - с использованием генераторов:
Qsort = qsort (x:xs) = qsort ++ [x] ++ qsort
Common Lisp
В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" - она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры 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)
Pascal
В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его - зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве - он проще и быстрее, хотя, теоретически, может быть хуже.
Внутреннее условие, помеченное комментарием «это условие можно убрать» - необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии - будут обменены местами. Что займёт больше времени - проверки или лишние перестановки, - зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.
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)
Стоит отметить, что быстрая сортировка может оказаться малоэффективной на массивах, состоящих из небольшого числа элементов, поэтому при работе с ними разумнее отказаться от данного метода. В целом алгоритм неустойчив, а также использование рекурсии в неверно составленном коде может привести к переполнению стека. Но, несмотря на эти и некоторые другие минусы, быстрая сортировка все же является одним из самых эффективных и часто используемых методов.
При написании статьи были использованы открытые источники сети интернет:
Каждое разделение требует, очевидно, Theta(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике. Однако, возможен случай таких входных данных, на которых алгоритм будет работать за O(n 2) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге... Вообще говоря, малореальная ситуация. Метод неустойчив. Поведение довольно естественно, если учесть, что при частичной упорядоченности повышаются шансы разделения массива на более равные части. Сортировка использует дополнительную память, так как приблизительная глубина рекурсии составляет O(log n), а данные о рекурсивных подвызовах каждый раз добавляются в стек. Из-за рекурсии и других "накладных расходов" Quicksort может оказаться не столь уж быстрой для коротких массивов. Поэтому, если в массиве меньше CUTOFF элементов (константа зависит от реализации, обычно равна от 3 до 40), вызывается сортировка вставками. Увеличение скорости может составлять до 15%. Для проведения метода в жизнь можно модифицировать функцию quickSortR, заменив последние 2 строки на If (j > CUTOFF) quickSortR(a, j);
if (N > i + CUTOFF) quickSortR(a+i, N-i);
Таким образом, массивы из CUTOFF элементов и меньше досортировываться не будут, и в конце работы quickSortR() массив разделится на последовательные части из <=CUTOFF элементов, отсортированные друг относительно друга. Близкие элементы имеют близкие позиции, поэтому, аналогично сортировке Шелла, вызывается insertSort(), которая доводит процесс до конца. Template Рассмотрим наихудший случай, когда случайно выбираемые опорные элементы оказались очень плохими(близкими к экстремумам). Вероятность этого чрезвычайно мала, уже при n = 1024 она меньше 2 -50 , так что интерес скорее теоретический, нежели практический. Однако, поведение "быстрой сортировки" является "эталоном" для аналогично реализованных алгоритмов типа "разделяй-и-властвуй". Не везде можно свести вероятность худшего случая практически к нулю, поэтому такая ситуация заслуживает изучения. Пусть, для определенности, каждый раз выбирается наименьший элемент a min . Тогда процедура разделения переместит этот элемент в начало массива и на следующий уровень рекурсии отправятся две части: одна из единственного элемента a min , другая содержит остальные n-1 элемента массива. Затем процесс повторится для части из (n-1) элементов.. И так далее.. Для исключения подобной ситуации можно заменить рекурсию на итерации, реализовав стек на основе массива. Процедура разделения будет выполняться в виде цикла. Псевдокод. Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.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
Псевдокод.
quickSort (массив a, верхняя граница N) {
Выбрать опорный элемент p - середину массива
Разделить массив по этому элементу
Если подмассив слева от p содержит более одного элемента,
вызвать quickSort для него.
Если подмассив справа от p содержит более одного элемента,
вызвать quickSort для него.
}
Реализация на Си.
templateМодификации кода и метода
При использовании рекурсивного кода, подобного написанному выше, это будет означать n вложенных рекурсивных вызовов функции quickSort.
Каждый рекурсивный вызов означает сохранение информации о текущем положении дел. Таким образом, сортировка требует O(n) дополнительной памяти.. И не где-нибудь, а в стеке. При достаточно большом n такое требование может привести к непредсказуемым последствиям.
Каждый раз, когда массив делится на две части, в стек будет направляться запрос на сортировку большей из них, а меньшая будет обрабатываться на следующей итерации. Запросы будут выбираться из стека по мере освобождения процедуры разделения от текущих задач. Сортировка заканчивает свою работу, когда запросы кончаются.
Итеративная QuickSort (массив a, размер size) {
Положить в стек запрос на сортировку массива от 0 до size-1.
do {
Взять границы lb и ub текущего массива из стека.
do {
1. Произвести операцию разделения над текущим массивом a.
2. Отправить границы большей из получившихся частей в стек.
3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.
} пока меньшая часть состоит из двух или более элементов
} пока в стеке есть запросы
}
Реализация на Си.
#define MAXSTACK 2048 // максимальный размер стека
template