Функция сортировки Шелла

Сортировка включениями с убывающим приращением

В 1959 г. Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сам метод сортировки объясняется и демонстрируется на стандартном примере (рис. 3.5). Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на 4 позиции. Такой процесс называется четвертной сортировкой. В нашем примере восемь элементов каждая группа состоит ровно из двух элементов. После первого прохода элементы перегруппировываются — теперь каждый элемент группы отстоит от другого на две позиции — и вновь сортируются. Это называется двойной сортировкой. Наконец, на третьем проходе идет обычная сортировка [1,3,9,10,13].

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

Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает (так как каждая /-сортировка объединяет две группы, уже отсортированные 2i-сортировкой). Очевидно так же, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу.

for (i=0; i < array_size; i++)

{

j = i;

temp = numbers[i];

while( (j >=increment)&&(numbers[j-increment]>temp]

{

numbers[j] = numbers[j - increment]; j = j - increment;

}

numbers[j

temp;

}

if (increment/2 != 0)

increment = increment/2; else if (increment == 1)

increment = 0; else

increment = 1;

| 44 | 55 | 12 | 42 | 94 | 18 || 06 ||"67