Метод Шелла

Сортировка Шелла (Donald Lewis Shell разработал алгоритм в 1959г.), называемая также «слиянием с обменом» является расширением челночной сортировки.

Алгоритм челночной сортировки действует точно также как стандартный обмен до тех пор, пока не возникает необходимость перестановки элементов исходного массива. Сравниваемый меньший элемент поднимается, насколько это возможно, вверх. Этот элемент сравнивается в обратном порядке со своими предшественниками, по направлению к первой позиции. Если он меньше предшественника, то выполняется обмен и начинается очередное сравнение. Когда элемент, передвигаемый вверх, встречает меньший элемент, этот процесс прекращается и нисходящее сравнение возобновляется с той позиции, в которой выполнялся первый обмен.

Сортировка заканчивается, когда нисходящее сравнение выходит на границу массива.

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

Реализовать метод Шелла можно следующим образом. Начальный шаг сортировки примем равным h=n/2, т.е. 0,5 от общей длины массива, и после каждого прохода будем уменьшать его в два раза. Каждый этап сортировки включает в себя проход всего массива и сравнение отстоящих на h элементов (i=0; j=n/2; i++; j++; до тех пор, пока j<n). Проход с тем же шагом повторяется, если элементы переставлялись. Заметим, что после каждого этапа отстоящие на h элементы отсортированы.

Таким образом, вначале сравниваются (и, если нужно, переставляются) далеко стоящие элементы, а на последнем проходе - соседние элементы.

Выигрыш получается за счет того, что на каждом этапе сортировки либо участвует сравнительно мало элементов, либо эти элементы уже довольно хорошо упорядочены, и требуется небольшое количество перестановок. Последний просмотр сортировки Шелла выполняется по тому же алгоритму, что и в челночной сортировке. Предыдущие просмотры подобны просмотрам челночной обработки, но в них сравниваются не соседние элементы, а элементы, отстоящие на заданное расстояние h. Большой шаг на начальных этапах сортировки позволяет уменьшить число вторичных сравнений на более поздних этапах.

Внешний цикл (1): от h=n/2 до h>0; h=h/2

Вложенный внутренний цикл (2): do (выполнять пока end_sort ==1):

1) end_sort = 0

2) цикл (3): для i от 0 до h; j от h; до тех пор, пока j<n; i++, j++

выполнить сравнение:

если x[i] > x[j] то переставить местами, т.е.

buf = x[j], x[j] = x[i], x[i] = buf;

изменить признак: end_sort = 1;

3) конец цикла (3)

Конец цикла (2): выполнять пока (end_sort= =1),

Конец цикла (1): каждый проход будет уменьшать шаг h в два раза.