Реализации алгоритмов/Сортировка/Быстрая: различия между версиями
Содержимое удалено Содержимое добавлено
Dm (обсуждение | вклад) →Pascal: дополнение |
|||
Строка 600:
=== Быстрая сортировка, нерекурсивный вариант ===
Нерекурсивная реализация быстрой сортировки через управляемый вручную [[w:стек|стек]].
Функции compare и change реализуются в зависимости от типа данных.
<source lang="pascal">
Строка 679:
end;
until stack=nil
end;
</source>
=== Частично рекурсивная реализация ===
Реализация на языке pascal с одной рекурсивной ветвью.
После разделения массива меньшая часть сортируется рекурсивным вызовом,
а бо'льшая - в цикле. Это гарантирует глубину рекурсии не более lg(N).
<source lang="pascal">
procedure qSort(var ar: array of real;);
procedure sort(var ar: array of real; low, high: integer);
var i, j: integer;
m, wsp: real;
begin
repeat
i:=low; j:=high; m:=ar[(i+j) div 2]; // Взятие среднего опорного элемента
repeat
while ar[i]<m do Inc(i);
while ar[j]>m do Dec(j);
if i<=j then begin
wsp:=ar[i]; ar[i]:=ar[j]; ar[j]:=wsp;
Inc(i); Dec(j);
end;
until i>j;
if (j - low) < (high - i) then begin // Сравнение размеров выделенных подмассивов
if low < j then qSort(ar, low, j); // Если первый подмассив меньше - он сортируется рекурсивно,
low := i; // а для следующего прохода цикла выбирается второй подмассив.
end
else begin // в противном случае всё наоборот
if i < high then qSort(ar, i, high); // Рекурсивно сортируется второй подмассив,
high := j; // а в следующем проходе цикла - первый.
end;
until low = high;
end;
begin
sort(ar, 0, High(ar));
end;
</source>
| |||