Метод пузырька

Алгоритм сортировки массива «пузырьковая сортировка» рассматривается практически во всех учебниках по программированию на С++. Его легко понять начинающим. Он наглядный и очень простой. На практике этот алгоритм почти никто не использует, так как он медлительный и есть более быстрые и усовершенствованные алгоритмы. Мы также разберем его потому, что сортировка «пузырьком» — это основа некоторых более эффективных алгоритмов, которые будут изложены в следующих статьях. Это «быстрая» сортировка, «пирамидальная» сортировка и «шейкерная» сортировка.

Как работает «пузырьковая» сортировка? Допустим у нас есть неотсортированный массив чисел из 5-ти элементов и нам предстоит разместить значения по возрастанию. Для наглядности, на рисунке изобразим этот массив вертикально «Исходный массив».

Алгоритм сортировки «пузырьком» состоит в повторении проходов по массиву с помощью вложенных циклов. При каждом проходе по массиву сравниваются между собой пары «соседних» элементов. Если числа какой-то из сравниваемых пар расположены в неправильном порядке — происходит обмен (перезапись) значений ячеек массива. Образно говоря в нашем примере 2 «легче» чем 3 — поэтому обмен есть, далее 2 «легче» чем 7 — снова обмен и т.д. При сравнении нулевого и первого элемента на нашем рисунке обмена нет, так как 2 «тяжелее» чем 1. Таким образом более «легкое» значение, как пузырек в воде, поднимается вверх до нужной позиции. Вот почему у этого алгоритма такое название.

Рассмотрим алгоритм сортировки «пузырьком» в работе:

#include <iostream>

using namespace std;

 

// прототип функции, которая выполнит сортировку "пузырьком"

void bubbleSort(int arrForSort[], const int SIZE);

 

void main()

{

setlocale(LC_ALL, "rus");

const int SIZE = 5;

int arr[SIZE];

 

cout << "Исходный массив:\n";

for (int i = 0; i < SIZE; i++)

{

arr[i] =  SIZE - i; // заполняем значениями по убыванию

cout << arr[i] << "\n__\n";

}

cout << "\n\n";

 

bubbleSort(arr, SIZE);  // передаем в функцию для сортировки

 

cout << "Массив после сортировки:\n";

for (int i = 0; i < SIZE; i++)

{

cout << arr[i] << "\n__\n";

}

cout << "\n\n";

}

 

void bubbleSort(int arrForSort[], const int SIZE)

{

int buff = 0; // для временного хранения значения, при перезаписи

 

for (int i = 0; i < SIZE - 1; i++) //

{

// вложенный цикл проходит от четвертого элемента

// до первого, находит с помощью if самое "легкое" значение,

// сравнивая соседние пары элементов,

// и поднимает его в нулевую ячейку массива

for (int j = SIZE - 1; j > i; j--)

{

if (arrForSort[j] < arrForSort[j - 1])

{

buff = arrForSort[j - 1];

arrForSort[j - 1] = arrForSort[j];

arrForSort[j] = buff;

}

}

// далее значение i увеличивается на 1

// и внутренний цикл будет перебирать элементы

// от четвертого до второго. Таким образом поднимет самое

// "легкое" значение из оставшихся  в первую ячейку и т.д.

}

}

Дополнить можно следующим: после того, как внутренний цикл отработает один раз, минимальное значение массива будет занимать нулевую ячейку. Поэтому при повторном проходе, очередное минимальное значение из оставшихся надо будет разместить в следующей ячейке (i + 1). Таким образом нет необходимости сравнивать между собой все элементы массива снова и количество обрабатываемых значений уменьшается на 1. При сортировке «пузырьком» необходимо пройти SIZE — 1 итераций внешнего цикла, так как сравнивать один элемент с самим собой — смысла нет.

Не будем забывать то, о чем мы говорили в самом начале — алгоритм «пузырьковой» сортировки малоэффективен и медлителен. Если у нас есть частично отсортированный массив и необходимо переместить в начало только одно значение, он все равно будет проходить все итерации циклов. То есть производить сравнение уже отсортированных значений массива, хотя этого уже можно и не делать.

Давайте немного улучшим эту ситуацию. Добавим в код еще одну переменную-«флажок», которая будет давать знать, произошел ли обмен значений на данной внешнего цикла итерации или нет. Перед тем, как войти во внутренний цикл, «флажок» будет сбрасываться в 0. Если обмен значениями в этом цикле случится — «флажку» будет присвоено значение 1, если нет — то он останется равным 0. В последнем случае (если «флажок» равен 0) — обменов не было и массив полностью отсортирован. Поэтому программе можно досрочно выйти из циклов, чтобы не тратить время попусту на последующие ненужные сравнения.

Рассмотрите следующий пример:

#include <iostream>

using namespace std;

 

void bubbleSort(int arrForSort[], const int SIZE);

 

int main()

{

setlocale(LC_ALL, "rus");

const int SIZE = 5;

int arr[SIZE] = {3, 4, 2, 5, 6};

 

cout << "Исходный массив:\n";

for (int i = 0; i < SIZE; i++)

{

cout << arr[i] << "\n__\n";

}

cout << "\n\n";

 

bubbleSort(arr, SIZE);  

 

cout << "Массив после сортировки:\n";

for (int i = 0; i < SIZE; i++)

{

cout << arr[i] << "\n__\n";

}

cout << "\n\n";

 

return 0;

}

 

void bubbleSort(int arrForSort[], const int SIZE)

{

int buff = 0;

int f; // "флаг"

for (int i = 0; i < SIZE - 1; i++)

{

f = 0;

for (int j = SIZE - 1; j > i; j--)

{

if (arrForSort[j] < arrForSort[j - 1])

{

buff = arrForSort[j - 1];

arrForSort[j - 1] = arrForSort[j];

arrForSort[j] = buff;

 

/* если хоть одна пара значений былы расположена неправильно

то есть условие if - верно, то присваиваем флагу значение 1*/

f = 1;

}

}

// если массив отсортирован и замен не было

// то есть f осталось равным 0 - прерываем цикл

if (f == 0)

break;

// для себя показываем количество проходов по массиву вложенным циклом

cout << i + 1 << "!!! \n";

}

cout << endl;

}

Видим такую картину после запуска:

Видно что программа прошла вложенным циклом по массиву 1 раз, переместила значение 2 в нужное место и завершила работу. А вот, что будет на экране, если закомментировать все строки кода, где есть переменная-«флажок»:

Программа вхолостую 4 раза «гоняла» по массиву, хотя значение 2 перемещено в нужную ячейку еще при первом проходе вложенным циклом.