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

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

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:

Страницы: 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

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