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

Метод Шелла является обобщением метода вставок и основан на том, что сортировка методом вставок выполняется очень быстро на почти отсортированном массиве данных. Он также известен как сортировка с убывающим шагом. В отличие от сортировки методом вставок при сортировке методом Шелла весь массив не сортируется одновременно: массив разбивается на отдельные сегменты, которые сортируются раздельно с помощью метода вставок.

Основная идея алгоритма состоит в том, что на начальном этапе реализуется сравнение и, если требуется, перемещение далеко отстоящих друг от друга элементов. Интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы, что приводит к перестановке соседних элементов на последних стадиях сортировки (если это необходимо).

Реализуем метод Шелла следующим образом. Начальный шаг сортировки примем равным n/2, т.е. ½ от общей длины массива, и после каждого прохода будем уменьшать его в два раза. Каждый этап сортировки включает в себя проход всего массива и сравнение отстоящих на gap элементов. Проход с тем же шагом повторяется, если элементы переставлялись. Заметим, что после каждого этапа отстоящие на gap элементы отсортированы. Рассмотрим пример.

 

Пример 15.5

Рассортировать массив чисел: 41, 53, 11, 37, 79, 19, 7, 61. В строке после массива в круглых скобках указаны индексы сравниваемых элементов и указан номер внешнего цикла.

 

41 53 11 37 79 19 7 61 – исходный массив

42 19 11 37 79 19 7 61 – (0, 4), (1, 5)

1-й цикл

41 19 7 37 79 19 11 61 – (2, 6), (3, 7)

 

7 19 41 37 11 53 79 61 – (0, 2), (1, 3), (2, 4), (3, 5), (4, 6), (5, 7)

2-й цикл

7 19 11 37 41 53 79 61 –

7 11 19 37 41 53 61 79 – (сравнивались соседние элементы) 3-й цикл

 

void sort_shell(int *x, int n)

{ int i, j; //две переменные цикла

int gap; //шаг сортировки

int sorted; //флаг окончания этапа сортировки

for(gap=n/2; gap> 0; gap/=2)//начало сортировки

do

{ sorted = 0;

for(i=0, j=gap; j< n; i++, j++)

if(*(x+i)> *(x+j))

{ swap((x+i), (x+j);

sorted = 1; }

}

while(sorted); }

Анализ сортировки методом Шелла

Сортировка методом Шелла будет выполняться для многих задач, в которых количество элементов в массиве данных небольшое. Любую возможность даже незначительного ускорения сортировки необходимо использовать.