3. Быстрая сортировка.
{быстрая сортировка}
procedure QuickSort(var item: DataArray; count:integer);
procedure qs(l, r: integer; var it: DataArray);
var
i, j: integer;
x, y: DataItem;
begin
i:=l; j:=r;
x:=it[(l+r) div 2];
repeat
while it[i]<x do i := i+1;
while x<it[j] do j := j-1;
if y<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it)
end;
begin
qs(1, count, item);
end;
type
DataItem = string[80];
DataArray = array [1..80] of DataItem;
{алгоритм быстрой сортировки для символьных строк }
procedure QsString(var item: DataArray; count:integer);
procedure qs(l, r: integer; var it:DataArray);
var
i, l: integer;
x, y: DataItem;
begin
i := l; j := r;
x := it[(l+r) div 2];
repeat
while it[i] < x do i := i+1;
while x < it[j] do j := j-1;
if i<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it);
end;
begin
qs(1, count, item);
end;
{быстрая сортировка записей с почтовым адресом}
procedure QsRecord(var item: DataArray; count:integer);
procedure qs(l, r:integer; var it:DataArray);
var
i, j: integer;
x, y: DataItem;
begin
i := l; j := r;
x := it[(l+r) div 2];
repeat
while it[i].name < x.name do i := i+1;
while x.name < it[j].name do j := j-1;
if i<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it)
end;
begin
qs(1, count, item);
end;
Основная стратегия ускорения алгоритмов сортировка - обмены между как можно более дальними элементами исходного файла - в методе быстрой сортировки реализована за счет того, что один из ключей в исходном файле используется для разделения его на два подфайла так, чтобы слева от выбранного элемента находились только элементы с меньшими ключами, а справа - только с большими. Элемент, разделяющий файл, помещается между его двумя подфайлами и процедура выполняется рекурсивно для каждой половины до тех пор, пока в очередном новом подфайле не окажется меньше, чем М элементов, где М - заранее выбранное число. Рассмотрим схему алгоритма.
Сортировка подфайлов, содержащих меньше чем М элементов, выполняется каким-либо простым методом, например простыми вставками. Таким образом, реализация метода зависит от двух параметров: значения М и способа выбора элемента, который предназначен для разделения файла на две части. Блок выбора Х в простейшем случае формулируется как X=K[l], однако это может привести к крайне неэффективному алгоритму. Наиболее простое лучшее решение - выбирать Х как случайный ключ из диапазона K[l] ... K[r] и обменять его с K[l].