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

Метод сортировки пузырьком на практике используется редко, в силу его слабой эффективности.

Суть метода заключается в переборе всех элементов массива и, если на текущей итерации некоторая пара соседних элементов массива расположены в неправильном порядке, то они меняются местами. После этого, перебор всех элементов начинается до отсортированного элемента на предыдущем проходе, и так далее до прохождения всех проходов (n). Таким образом, после каждого прохода самый «легкий» элемент окажется на самом верху перед более «легкими» элементами. Если образно представить массив вертикально от 0-го элемента сверху и n-1 элемента снизу (где n – кол-во элементов массива), то при каждом проходе по одному «легкому» элементу массива будут подниматься наверх, как пузырьки, отсюда и название метода.

Переведем эту задачу в алгоритм для написания в дальнейшем его кода:

1. Так, как нужно повторить «всплытие» для каждого элемента массива, нужно создать цикл, с кол-вом итераций, равным кол-ву элементов массива. Каждое «всплытие» элемента будет устанавливаться в начало массива до более «легкого» элемента, т.к. на каждом следующем проходе будут «всплывать» все более «тяжелые» элементы, поэтому ориентируем цикл от минимального к максимальному индексам:

for (i=0; i< size; i++)

2. Для «всплытия» более «легкого» элемента наверх, перебираем массив от нижнего элемента до элемента, который уже «всплыл» на предыдущих проходах. Для этого создаем внутренний цикл с счетчиком-переменной, меняющейся от нижнего индекса массива до уже упорядоченного элемента i:

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

3. Для «всплытия» более «легкого» элемента наверх, поменяем местами соседнюю пару элементов, если они находятся в неправильном порядке. Для замены местами, используем вспомогательную переменную:

if (array[j-1]> array[j]) {

x=array[j-1];

array[j-1]=array[j];

array[j]=x;

}

Таким образом, блок-схема и весь алгоритм выглядит так:

Рис. 1.1. Блок-схема сортировки Пузырьком

long i, j, x;

for (i=0; i< size; i++){

for (j=size-1; j> i; j--){

if (array[j-1]> array[j]) {

x=array[j-1];

array[j-1]=array[j];

array[j]=x;

}

}

}

Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta(n²), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен. Поскольку одинаковые элементы не меняются местами, можно сделать вывод, что алгоритм устойчивый. Поведение алгоритма неестественное, т.к. по уже отсортированным до алгоритма элементам, также делаются проходы и сравнения.