Программирование на языке С
Страница 74. Пузырьковая сортировка


 

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

Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'=, в котором для любого 1<=i<=n элемент K'(i) <="K'(i+1)."

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

Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.

Пример:

 B=<20,-5,10,8,7>, исходный список;
B1=<-5,10,8,7,20>, первый просмотр;
B2=<-5,8,7,10,20>, второй просмотр;
B3=<-5,7,8,10,20>, третий просмотр.

В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса 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<=n; i++) if ( a[i] < a[i-1] ) { c="a[i];" a[i]="a[i-1];" a[i-1]="c;" is="1;" } } return(a); }

Пузырьковая сортировка выполняется при количестве действий Q=(n-m)*(n-m) и не требует дополнительной памяти.

 
« Предыдущая статья   Следующая статья »