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

       

Сортировка с помощью прямого обмена (пузырьковая сортировка)


Классификация методов сортировки редко бывает осмысленной. Оба разбиравшихся до этого метода можно тоже рассматривать как "обменные" сортировки. В данном же, однако, разделе  описан метод, где обмен местами двух элементов представляет собой характернейшую особенность процесса. Изложенный ниже алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы.

Как и в упоминавшемся методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу (см. рис.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),

а перемещения вообще отсутствуют

Сравнительный анализ прямых сортировок показывает, что обменная "сортировка"  в классическом виде представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора. Если же в нее внесены приведенные выше усовершенствования, то для достаточно  упорядоченных массивов пузырьковая сортировка даже имеет преимущество.



Содержание раздела