Практика программирования (Бейсик, Си, Паскаль)
Сортировка больших массивов - часть 5
Затем аналогичный прием применяют к каждой из полученных половин. В каждой из них выбирается свой средний элемент и относительно него осуществляются необходимые перестановки. Как следует из описания, алгоритм Хоара очень хорошо укладывается в понятие рекурсивной процедуры. Для единообразия в обращении процедура быстрой сортировки представлена в виде двух процедур — внешней hoar, к которой обращается пользователь, и внутренней — quick. Последняя выполняет рекурсивную обработку подмассива, заданного граничными значениями индексов — left и right.
Подпрограмма hoare.bas
SUB HOARE(X% (),N%)
QUICK X%(),0,N%-1
END SUB
SUB QUICK(X%(),LEFT%,RIGHT%)
DIM I,J,XX,YY
I=LEFT%: J=RIGHT%
XX=X((LEFT%+RIGHT%)\2)
DO
WHILE X%(I) < XX AND I < RIGHT%: I=I+1: WEND
WHILE XX < X%(J) AND J > LEFT%: J=J-1: WEND
IF I <= J THEN
YY=X%(I): X%(I)=X%(J): X%(J)=YY: 1=1+1: J=J-1
END IF
LOOP WHILE I <= J
IF LEFT% < J THEN QUICK X%(),LEFT%,J
IF I < RIGHT% THEN QUICK X%(),I,RIGHT%
END SUB
Функция hoare.c
void hoare(int *x,int n) {
quick(x,0,n-1);
return;
}
/*--------------------------------*/
void quick(int *x, int left, int right) {
register int i,j;
int xx,tmp;
i=left;
j=right;
xx=x[(left+right)/2];
do
{
while (x[i] < xx && i < right) i++;
while (xx < x[j] && j > left) j--;
if (i<=j)
{
tmp=x[ i ] ;
x[i]=x[j];
x[j]=tmp;
i++; j-- ;
}
}
while(i<=j);
if(left < j) quick(x,left,j);
if(i < right) quick(x,i,right);
}
Процедура hoare.pas
procedure quick(var x:array of integer;left,right:integer);
var
i,j,xx,tmp:integer;
begin
i:=left; j:=right;
xx:=x[(left+right) div 2];
repeat
while (x[i] < xx) and (i < right) do i:=i+l;
while (xx < x[j]) and (j > left) do j:=j-l;
if i<=j then
begin
tmp:=x[i];
x[i]:=x [j];
x[j]:=tmp;
i:=i+l;
j:=j-i;
end;
until i>j;
if left < j then quick(x,left,j);
if i < right then quick(x,i,right);
end;
procedure hoare(var x:array of integer;n:integer);
begin
quick(x,0,n-l);
end;
