<< Пред. стр. 8 (из 19) След. >>
Список литературы по разделу
return
Паскаль:
Без барьера:
for i:= 2 to n do
begin
x:= a(i);
for j:= i - 1downto 1 do
if x < a(j ) then
a(j +1):= a(j )
else goto 1;
end;
end;
1: a(j + 1):= x;
end;
end;
С барьером:
for i := 2 to n do
begin
x:= a(i);
a(0):= x; {a(0) - барьер}
j:= i - 1;
while x < a(j ) do
begin
a(j +1):= a(j );
j:=j - 1;
end;
a(j +1):= x;
end;
Эффективность алгоритма
Число сравнений ключей Ci при i- м просеивании самое большее равно i-1, самое меньшее - 1; если предположить, что все перестановки из N ключей равновероятны, то среднее число сравнений = i/2. Число же пересылок Mi=Ci+3 (включая барьер). Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки - когда они первоначально расположены в обратном порядке. В некотором смысле сортировка с помощью включения демонстрирует истинно естественное поведение. Ясно, что приведенный алгоритм описывает процесс устойчивой сортировки: порядок элементов с равными ключами при нем остается неизменным.
Количество сравнений в худшем случае, когда массив отсортирован противоположным образом, Сmax = n(n - 1)/2, т. е. - О (n2). Количество перестановок Mmax = Cmax + 3(n-1), т.е. - О (n2). Если же массив уже отсортирован, то число сравнений и перестановок минимально: Cmin = n-1; Mmin = =3(n-1).
6.2 Сортировка методом прямого выбора
Этот прием основан на следующих принципах:
1. Выбирается элемент с наименьшим ключом.
2. Он меняется местами с первым элементом a 1.
3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый "большой" элемент.
Алгоритм формулируется так:
for i = 1 to n - 1
x = a(i)
k = i
for j = i + 1 to n
if a(j) < x then
k = j
x = a(k)
endif
next j
a(k) = a(i)
a(i) = x
next i
return
for i := 1 to n - 1 do
begin
x := a[i];
k := i;
for j := i + 1 to n do
if a[j] < x then
begin
k := j;
x := a[k];
end;
a[k] := a[i];
a[i] := x;
end;
Эффективность алгоритма:
Число сравнений ключей C, очевидно, не зависит от начального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для C при любом расположении ключей имеем:
C = n(n-1)/2
Порядок числа сравнений, таким образом, О(n2)
Число перестановок минимально Мmin = 3(n - 1) в случае изначально упорядоченных ключей и максимально, Мmax = 3(n - 1) + С, т.е. порядок О(n2), если первоначально ключи располагались в обратном порядке.
В худшем случае сортировка прямым выбором дает порядок n2, как для числа сравнений, так и для числа перемещений.
6.3. Сортировка с помощью прямого обмена (пузырьковая сортировка)
Классификация методов сортировки редко бывает осмысленной. Оба разбиравшихся до этого метода можно тоже рассматривать как "обменные" сортировки. В данном же, однако, разделе описан метод, где обмен местами двух элементов представляет собой характернейшую особенность процесса. Изложенный ниже алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы.
Как и в упоминавшемся методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу (см. рис.6.3).
Такой метод широко известен под именем "пузырьковая сортировка". В своем простейшем виде он представлен ниже.
Программы на псевдокоде и Паскале:
for i = 2 to n
for j = n to i step -1
if a(j) < a(j - 1) then
x = a(j - 1)
a(j - 1) = a(j)
a(j) = x
endif
next j
next i
return
for i := 2 to n do
for j := n downto i do
if a[j] < a[j - 1]then
begin
x := a[j - 1];
a[j - 1] := a[j];
a[j] := x;
end;
end;
end;
В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не переставлять элементы, можно ввести флажок fl, который остается в значении false , если при очередном проходе не будет произведено ни одного обмена. На нижеприведенном алгоритме добавления отмечены курсивом.
fl = true
for i = 2 to n
if fl = false then return
endif
fl = false
for j = n to i step -1
if a(j) < a(j - 1) then
fl = true
x = a(j - 1)
a(j - 1) = a(j)
a(j) = x
endif
next j
next i
return
Улучшением пузырькового метода является шейкерная сортировка, где после каждого прохода меняют направление во внутреннем цикле.
Эффективность алгоритма:
Число сравнений Cmax = n(n-1)/2 , О(n2).
Число перемещений Мmax=3Cmax=3n(n-1)/2, О(n2).
Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений
Cmin = n - 1, О(n),
а перемещения вообще отсутствуют
Сравнительный анализ прямых сортировок показывает, что обменная "сортировка" в классическом виде представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора. Если же в нее внесены приведенные выше усовершенствования, то для достаточно упорядоченных массивов пузырьковая сортировка даже имеет преимущество.
6.4. Улучшенные методы сортировки
6.4.1. Быстрая сортировка (Quick Sort)
Относится к методам обменной сортировки. В основе лежит методика разделения ключей по отношению к выбранному.
Слева от 6 располагают все ключи с меньшими, а справа - с большими или равными 6 (рис. 6.4).
Sub Sort (L, R)
i = L
j = R
x = a((L + R) div 2)
repeat
while a(i) < x do
i = i + 1
endwhile
while a(j) > x do
j = j - 1
endwhile
if i <= j then
y = a(i)
a(i) = a(j)
a(j) = y
i = i + 1
j = j - 1
endif
until i > j
if L < j then
sort (L, j)
endif
if i < R then
sort (i, R)
endif
return
sub QuickSort
sort (1, n)
return
procedure Sort (L, R: integer);
begin
i := L;
j := r;
x := a[(L + r) div 2];
repeat
while a[i] < x do
i := i + 1;
while a[j] > x do
j := j - 1;
if i <= j then
begin
y := a[i];
a[i] := a[j];
a[j] := y;
i := i + 1;
j := j - 1
end;
until i > j;
if L < j then sort (L, j);
if i < r then sort (i, r);
end;
procedure QuickSort;
begin
sort (1, n);
end;
Эффективность алгоритма:
О(n log n) - самый эффективный метод.
6.4.2 Сортировка Шелла (сортировка с уменьшающимся шагом)
В 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. К какому из основных методов относится метод Шелла?
7. ПРЕОБРАЗОВАНИЕ КЛЮЧЕЙ (РАССТАНОВКА)
Метод расстановок (хеширования) направлен на быстрое решение задачи о местоположении элемента в структуре данных. В методе расстановок данные организованы как обычный массив. Поэтому Н - отображение, преобразующее ключи в индексы массива, отсюда и появилось название «преобразование ключей», обычно даваемое этому методу. Следует заметить, что нет никакой нужды обращаться к каким-либо процедурам динамического размещения, ведь массив — это один из основных, статических объектов. Метод преобразования ключей часто используется для таких задач, где можно с успехом воспользоваться и деревьями.
<< Пред. стр. 8 (из 19) След. >>
Список литературы по разделу