Практика программирования (Бейсик, Си, Паскаль)



Сортировка больших массивов - часть 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;




Содержание  Назад  Вперед