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;

В нашем случае получился один проход “вхолостую”. Об этом говорит сайт https://intellect.icu . Чтобы лишний раз не переставлять элементы, можно ввести флажок 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


Улучшением пузырькового метода является шейкерная сортировка, где после каждого прохода меняют направление во внутреннем цикле.


Эффективность алгоритма:

Число сравнений C_max = n(n-1)/2 , О(n²).

Число перемещений М_max=3C_max=3n(n-1)/2, О(n²).

Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений

C_min = n - 1, О(n),

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

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

На этом все! Теперь вы знаете все про сортировка с помощью прямого обмена пузырьковая сортировка , Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое сортировка с помощью прямого обмена пузырьковая сортировка и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных

Из статьи мы узнали кратко, но содержательно про сортировка с помощью прямого обмена пузырьковая сортировка