Практика программирования (Бейсик, Си, Паскаль)
Метод Ч. Э. Р. Хоара,
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 г., издалека напоминает способ ловли льва в пустыне "методом Вейерштрасса". Сначала пустыню делят пополам и выбирают ту половину, в которой находится лев. Затем эту половину снова делят пополам и так продолжают до тех пор, пока область, содержащая льва, не помещается в клетку. В математике подобный метод применяют для нахождения корня функции, принимающей на концах отрезка разные знаки. Это и есть метод Вейерштрасса, более известный под названием "метода деления пополам".
Хоар применил подобный подход к сортировке и предложил следующий алгоритм. Выберем какой-то средний элемент последовательности хх (обычно в качестве такового выбирают средний элемент). Если он стоит на своем месте (имеется в виду ситуация, когда последовательность упорядочена), то все элементы, расположенные левее, не больше хх, а элементы, находящиеся правее, — не меньше хх. Поэтому первый шаг быстрой сортировки заключается в том, чтобы перенести в левую часть массива те элементы правой половины, которые меньше хх, а в правую часть — те элементы из левой половины, которые больше хх. Обычно при этом поиск ведут в обе стороны от хх и как только обнаруживают пару, нарушающую порядок, производят обмен.
