Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 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.В чем состоит суть метода прямого обмена?

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники