Сортировка Шелла (сортировка с уменьшающимся шагом)
В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью метода прямого включения. Работа его представлена на рис. 6.5:
Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. После первого прохода элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на 2 позиции - и вновь сортируются. Это называется двойной сортировкой. И, наконец, на третьем проходе идет обычная или одиночная сортировка.
На первый взгляд можно засомневаться: если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако, на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок.
Ясно, что такой метод в результате дает упорядоченный массив, и, конечно, сразу же видно, что каждый проход от предыдущих только выигрывает; также очевидно, что расстояния в группах можно уменьшать по разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу.
Приводимый алгоритм основан на методе прямой вставки без барьера и не ориентирована на некую определенную последовательность расстояний, хотя в нем для конкретности заданы шаги 5, 3 и 1.
При использовании метода барьера каждая из сортировок нуждается в постановке своего собственного барьера, и программу для определения его местонахождения необходимо делать насколько возможно простой. Поэтому приходится расширять массив до [-h1..N].
h[1..t] - массив размеров шагов
a[1..n] - сортируемый массив
k - шаг сортировки
x - значение вставляемого элемента
| Subroutine ShellSort
Псевдокод: const t = 3 h(1) = 5 h(2) = 3 h(3) = 1 for m = 1 to t k = h(m) for i = k + 1 to n x = a(i) for j = i - k to 1 step -k if x < a(j) then a( j+k) = a(j) else goto L endif next j L: a(j+k) = x next i next m return | Паскаль:
const t = 3; h(1) = 5; h(2) = 3; h(3) = 1; var h: array [1..t] of integer; a: array [1..n] of integer; k, x, m, t, i, j: integer; begin for m = 1 to t do begin k:= h(m); for i = k + 1 to n do begin x:= a(i); for j = i-k downto k do begin if x < a(j ) then a(j+k):= a(j); else goto 1; end ; end; end; 1: a(j+1) = x ; end; end . |
Не доказано, какие расстояния дают наилучший результат, но они не должны быть множителями один другого.
Д. Кнут предлагает такую последовательность шагов (в обратном порядке): 1, 3, 7, 15, 31, … То есть: h m-1 = h m + 1,
t = log2n - 1. При такой организации алгоритма его эффективность имеет порядок O ( n1.2)
Контрольные вопросы
1. Что такое сортировка?
2. Назовите основные методы сортировки.
3. Какие методы сортировки относятся к строгим?
4. Какие методы сортировки относятся к улучшенным?
5. Какая сортировка называется устойчивой?
6. В чем состоит суть метода прямого включения?
7. В чем состоит суть метода прямого выбора?
8. В чем состоит суть метода прямого обмена?
9. Назовите разницу между этими тремя методами.
10. Какой метод сортировки является самым эффективным?
11. К какому из основных методов относится метод Шелла?
