Пузырьковая сортировка
Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=< K1, K2,..., Kn >. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'=< K'1, K'2,...,K'n >, в котором для любого 1При обменной сортировке упорядоченный список В' получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.
Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.
Пример:
B=, исходный список; B1=, первый просмотр; B2=, второй просмотр; B3=, третий просмотр.
В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса n до индекса m) в порядке возрастания элементов.
Нижеприведенная функция bubble сортирует входной массив методом пузырьковой сортировки.
/* сортировка пузырьковым методом */ float * bubble(float * a, int m, int n) { char is=1; int i; float c; while(is) { is=0; for (i=m+1; i
Пузырьковая сортировка выполняется при количестве действий Q=(n-m)*(n-m) и не требует дополнительной памяти.
