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) и не требует дополнительной памяти.

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

Упорядоченный массив 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.

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

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

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

Например:

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. При сортировке посредством выбора требуется Q=(n-m)*(n-m) действий и не требуется дополнительной памяти.

Сортировка квадратичной выборкой. Исходный список В из N элементов делится на М подсписков В1,В2,...,Вm, где М равно квадратному корню из N, и в каждом В1 находится минимальный элемент G1. Наименьший элемент всего списка В определяется как минимальный элемент Gj в списке , и выбранный элемент Gj заменяется новым наименьшим из списка Bj. Количество действий, требуемое для сортировки квадратичной выборкой, несколько меньше, чем в предыдущих методах Q= N*N, но требуется дополнительная память для хранения списка G.