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

Сортировка пузырьком (Bubble sort) – простой алгоритм сортировки обменами, который считается учебным и практически не применяется вне учебной литературы.

Пусть задан массив из n элементов. Для сортировки его элементов метод «пузырька» будет иметь следующую последовательность шагов.

1. Шаг инициализации. Для каждого прохода позиция последней перестановки элементов LastExchange принимается равной номеру последнего элемента массива n-1.

2. Шаг итерации. Для всех элементов с нулевой позиций до позиции последнего обмена производится сравнение со следующим элементом. Если текущий элемент оказывается больше следующего, то они переставляются, и позиция последнего обмена устанавливается равной текущему элементу.

3. Шаг выхода. Первый и второй шаги повторяются до тех пор, пока позиция последнего обмена не станет равной нулю.

 

Пример

Пусть дан следующий массив:

Проход 1

Проход 2

Оченка вычислительной сложности алгоритма показывает, что в наилучшем случае без учета LastExchange будет , т.е. .

Однако, на каждом (n-1) проходе сравниваемые элементы в наихудшем случае (когда массив отсортирован по убыванию) придется переставлять , т.е. число перестановок будет иметь порядок сложности . В наилучшем случае, когда массив отсортирован по возрастанию и используется позиция последней перестановки LastExchange, число сравнений будет (n-1), а перестановок не будет. Анализ общего случая затруднен из-за случайности обмена. Однако, из-за большого количества перестановок данный алгоритм является самый медленный из всех существующих.

Блок-схема алгоритма сортировки методом «пузырька» имеет следующий вид:

Реализовать данный алгоритм можно следующим образом:

 

template <class T>

void BubbleSort(T *A, const int n)

{

T temp;

int i=n-1, LastExchange=n-1;

while (i > 0)

{

i = 0;

for (int j = 0; j < LastExchange; j++)

if (A[j] > A[j+1])

{

Temp = A[j];

A[j] = A[j+1];

A[j+1]= temp;

i = j;

}

LastExchange = i;

}

}