logo search
УП_САОД_2003

Сортировка методом Шелла

Метод Шелла является усовершенствованием метода простого включения, который основан на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент A[i] фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части. (На самом деле передвигалось место, оставленное под A[i]). Метод Шелла позволяет преодолеть это ограничение следующим интересным способом.

Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i-h], A[i-2h], A[i-3h] и так далее, где h – положительная константа. Таким образом, формируется массив, в котором «h – серии» элементов, отстоящих друг от друга на h, сортируются отдельно.

Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h=1.

В настоящее время неизвестна последовательность hi, hi-1, hi-2, ..., h1, оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что hi+1=3hi+1, а h1=1. Начинается процесс с hm, что hm[n/9]. Иногда значение h вычисляют проще: hi+1=hi/2, h1=1, hm=n/2. Это упрощенное вычисление h и будем использовать далее.

Теперь запишем алгоритм.

procedure ShellSort(n: integer;

var A: array[1..n] of integer);

{Процедура сортировки Шелла}

var

h, i, j, Tmp: integer;

begin

{Вычисляем величину h}

h := n div 2;

{Собственно сортировка}

while h > 0 do begin

for i := 1 to n-h do begin

j := i;

while j > 0 do begin

{Сравниваем элементы, отстоящие друг от друга}

{на расстояние, кратное h}

if A[j] > A[j+h] then begin

{Меняем элементы}

Tmp := A[j+h];

A[j+h] := A[j];

A[j] := Tmp;

j := j - h;

end else begin

{Досрочно завершаем цикл с параметром j}

j := 0;

end;

end;

end;

{Уменьшаем размер серии}

h := h div 2;

end;

end;

Рисунок 42. Сортировка Шелла

Как показывают теоретические выкладки, которые здесь приводить не будем, сортировке методом Шелла требуется в среднем 1,66n1,25 перемещений. Порядок элементов влияет на количество итераций внутреннего цикла while. Дополнительной памяти данный алгоритм не требует, но и не гарантирует сохранение порядка элементов с одинаковыми значениями.