Метод Хоара (Hoare)
В алгоритме Хоара сначала выбирается так называемое опорное значе-
ние. Затем элементы со значением, меньше опорного, переносятся влево, а
со значением, большим или равным ему, - вправо. Таким образом, на первом
шаге алгоритм Хоара делит элементы на два раздела: со значениями, мень-
шими опорного, и со значениями, большими или равными ему. Затем под-
программа, рекурсивно вызывая сама себя, продолжает разбивку разделов.
В каждом разделе выбирается новое опорное значение, и элементы раздела
переставляются влево и вправо. Процесс разбивки на разделы рекурсивно
продолжается до тех пор, пока размер раздела достигнет одного или двух
элементов. Эффективность метода зависит от объема данных и выбора ме-
тода опорного сечения. В приведенном ниже алгоритме в качестве опорного
выбирается средний элемент раздела. Процедура сортировки Хоара имеет
вид
Procedure QuickSort(var a:vec; low,high:integer);
var l,r:integer; // Метод Хоара
op,w:extended;
begin
op:=a[(low+high) div 2]; // Опорный элемент
// Перенос элементов, меньших опорного, влево, а
больших - вправо
l:=low; r:=high;
repeat
while (l<=high) and (a[l]<op) do inc(l);
while (r>=low) and (a[r >op) do dec(r);
if l<=r then begin
w:=a[l]; a[l]:=a[r]; a[r]:=w;
inc(l); dec(r);
end;
until l>r;
if r>low then QuickSort(a,low,r);
if l<high then QuickSort(a,l,high);
end;