Сортировка методом пузырьков

Расположим элементы массива сверху вниз – в первой строке x [0] , во второй – x [1] и т.д. Рассмотрим последний элемент массива x [ n -1] и сравним его с предшествующим. Если он меньше, то переставим эти два элемента x [ n ­1] и x [ n -2] . Затем x [ n -2] сравним с предшествующим. Если , то поменяем эти элементы местами. После многократного повторения этого процесса наименьший элемент массива «всплывает» наверх, как самый «легкий».

Затем аналогичным образом находим наименьший элемент среди и ставим его на место x [1] , затем среди и т.д.

Пример. Рассмотрим преобразования массива, состоящего из 5 элементов методом пузырьков:

x [0]=35 23 23 23 23 23

x [1]=23 35 26 26 26 26

x [2]=42 26 35 31 31 31

x [3]=26 42 31 35 35 35

x [4]=31 31 42 42 42 42

Вставка наименьшего элемента осуществляется с помощью цикла

for (i=n-1; i>j; i--)

if (x[i]<x[i-1]) swap (i, i-1);

в результате которого x [ j ] становится наименьшим элементом среди

Здесь swap ( p , q ) – подпрограмма, переставляющая элементы x [ p ] и x [ q ] . Цикл достаточно выполнить для

Получаем следующий двойной цикл, сортирующий массив методом пузырьков:

for (j=0; j<n-1; j++)

for (i=n-1; i<j; i--)

if (x[i-1]>x[i])

{

temp=x[i-1]; x[i-1]=x[i]; x[i]=temp;

}

Количество копирований в худшем случае равно

Число сравнений равно