15. Линейная сортировка, метод пузырька.

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

При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка и для ее решения существуют различные методы. Рассмотрим некоторые из них.

Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=. Требуется переставить элементы списка В так, чтобы получить упорядоченный список 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) и не требует дополнительной памяти.

17. Сортировка вставкой, посредством выбора.

Сортировка вставкой

Упорядоченный массив B' получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,...,N выполняется вставка узла Кi в B' так, что B' остается упорядоченным списком длины i.

Например, для начального списка B=<20,-5,10,8,7> имеем:

B=<20,-5,10,8,7> B'=<> B=<-5,10,8,7> B'=<20> B=<10,8,7> B'=<-5,20> B=<8,7> B'=<-5,10,20> B=<7> B'=<-5,8,10,20> B=<> B'=<-5,7,8,10,20> Функция insert реализует сортировку вставкой.

/* сортировка методом вставки */ float *insert(float *s, int m, int n) { int i,j,k; float aux; for (i=m+1; i<=n; i++) { aux="s[i]"; for (k="m"; k<="i" && s[k]=k; j--) s[j+1]=s[j]; s[k]=aux; } return(a); } Здесь оба списка В и В' размещаются в массиве s, причем список В занимает часть s c индексами от i до n, а B' - часть s c индексами от m до i-1 (см. рис.26).

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

Сортировка посредством выбора

Упорядоченный список В' получается из В многократным применением выборки из В минимального элемента, удалением этого элемента из В и добавлением его в конец списка В', который первоначально должен быть пустым.

Например:

B=<20,10,8,-5,7>, B'=<> B=<20,10,8,7>, B'=<-5> B=<20,10,8>, B'=<-5,7> B=<20,10>, B'=<-5,7,8> B=<20>, B'=<-5,7,8,10> B=<>, B'=<-5,7,8,10,20> . Функция select упорядочивает массив s сортировкой посредством выбора.

/* сортировка методом выбора */ double *select( double *s, int m, int n) { int i,j; double c; for (i=m; is[j]) { c=s[i]; s[i]=s[j]; s[j]=c; } return(s); } Здесь, как и в предыдущем примере оба списка В и В' размещаются в разных частях массива s (см. рис.27). При сортировке посредством выбора требуется Q=(n-m)*(n-m) действий и не требуется дополнительной памяти.