Реализации алгоритмов/Сортировка/Быстрая: различия между версиями

 

== [[w:Pascal|Pascal]] ==

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

 

 

procedure quicksort(var a: list; Lo,Hi: integer);

 

procedure sort(l,r: integer);

 

=== Частично рекурсивная реализация ===

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

 

<source lang="pascal">

end;

until i>j;

if low < j then qSort(ar, low, j); // Если первый подмассив меньше - он сортируется рекурсивно,

low := i; // а для следующего прохода цикла выбирается второй подмассив.

end

if i < high then qSort(ar, i, high); // Рекурсивно сортируется второй подмассив,

high := j; // а в следующем проходе цикла - первый.

until low = high;

end;