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




Сортировка больших массивов - часть 4


X(J+GAP)=X(J)

NEXT J X(J+GAP)=XX

NEXT I

NEXT К

END SUB

Функция shell.с

void shell(int *x,int n) {

register int i,j,gap,k; int xx;

char a[5]={9,5,3,2,l};

for(k=0; k<5; k++) {

gap=a[k];

for(i=gap; i<n; ++i) {

xx=x[i];

for(j=i-gap; xx < x[j] && j >= 0; j=j-gap)

x[j+gap]=x[j); x[j+gap]=xx; } } }

Процедура shell.pas

procedure shell(var x:array of integer;n:integer) ;

var

i,j,k,gap,xx:integer;

const

a:array [0..4] of byte=(9,5,3,2,1};

begin

for k:=0 to 4 do

begin

gap:=a[k];

for i:=gap to n-1 do begin

xx:=x[i];

j:=i-gap;

while (j >= 0) and (xx < x[j]) do

begin

x[j+gap]:=x[j];

j:=j-gap;

end;

x[j+gap]:=xx;

end;

end;

end;

Сортировка методом Хоара (quicksort)

Метод Ч. Э. Р. Хоара, опубликованный в 1962 г., издалека напоминает способ ловли льва в пустыне "методом Вейерштрасса". Сначала пустыню делят пополам и выбирают ту половину, в которой находится лев. Затем эту половину снова делят пополам и так продолжают до тех пор, пока область, содержащая льва, не помещается в клетку. В математике подобный метод применяют для нахождения корня функции, принимающей на концах отрезка разные знаки. Это и есть метод Вейерштрасса, более известный под названием "метода деления пополам".

Хоар применил подобный подход к сортировке и предложил следующий алгоритм. Выберем какой-то средний элемент последовательности хх (обычно в качестве такового выбирают средний элемент). Если он стоит на своем месте (имеется в виду ситуация, когда последовательность упорядочена), то все элементы, расположенные левее, не больше хх, а элементы, находящиеся правее, — не меньше хх. Поэтому первый шаг быстрой сортировки заключается в том, чтобы перенести в левую часть массива те элементы правой половины, которые меньше хх, а в правую часть — те элементы из левой половины, которые больше хх. Обычно при этом поиск ведут в обе стороны от хх и как только обнаруживают пару, нарушающую порядок, производят обмен.




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