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

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

Количество сравнений в худшем случае, когда массив отсортирован противоположным образом, С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

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

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