Метод бульбашкового сортування

Метод "бульбашкового сортування" ґрунтується на перестановці сусідніх елементів. Для впорядкування елементів масиву здійснюються повторні проходи по масиву.

Переміщення елементів масиву здійснюється таким чином: масив переглядається зліва направо, здійснюється порівняння пари сусідніх елементів; якщо елементи в парі розміщені в порядку зростання, вони лишаються без змін, а якщо ні - міняються місцями.

В результаті першого проходу найбільше число буде поставлено в кінець масиву. У другому проході такі операції виконуються над елементами з першого до (N-1)-ого, у третьому - від першого до (N-2)-ого і т.д. Впорядкування масиву буде закінчено, якщо при проході масиву не виконається жодної перестановки елементів масиву. Факт перестановки фіксується за допомогою деякої змінної (у наступному прикладі - is), яка на початку має значення 0 і набуває значення 1 тоді, коли виконається перестановка в якій-небудь парі.

Масив до впорядкування			-1	-40		-75	-22
Перший перегляд масиву		-1	-40		-75	-22
Другий перегляд масиву	-1	-40		-75	-22
Третій перегляд масиву	-40	-1	-75	-22
Четвертий перегляд масиву	-40	-75	-22	-1
П'ятий перегляд масиву	-75	-40	-22	-1

Рис. 1.15. Бульбашкове сортування

const n=10;

int a[n], i, c, is;

/* … */

do {

is=0;

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

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

{

c=a[i];

a[i]=a[i-1];

a[i-1]=c;

is=1;

}

} while (is);