Пузырьковая сортировка

Сравниваются и меняются местами при необходимости пары элементов. Можно начать перебирать пары с первой или же с последней. Рассмотрим вариант перебора пар с последней. В результате первого просмотра всех пар самый маленький элемент массива оказывается самым левым (эффект пузырька). Процесс повторяется с оставшимися элементами массива. Результаты первых трех просмотров приведены в таблицах 8.3–8.5.

Таблица 8.3 – Результат первого просмотра массива методом пузырьковой сортировки

				94

Таблица 8.4 – Результат второго просмотра массива методом пузырьковой сортировки

	18

Таблица 8.5 – Результат третьего просмотра массива методом пузырьковой сортировки

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

for(int i=1;i<n;i++){

bool flag=1;

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

if(a[j]<a[j-1]){

int tmp=a[j];

a[j]=a[j-1];

a[j-1]=tmp;

flag=0;

}

if(flag)

break;

}

Сортировка устойчивая. В общем случае это одна из самых медленных сортировок, но она легко справляется с частично отсортированными массивами, имеющими лишь небольшие возмущения (а не такие ли массивы мы используем наиболее часто?).