3. Сортировка и слияние

При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка. Сортировку следует понимать именно как процесс перегруппировки однотипных элементов структуры данных в некотором определенном порядке. Цель сортировки – облегчить последующие поиск, обновление, исключение, включение элементов в структуру данных. На отсортированных данных легче определить, имеются ли пропущенные элементы, все ли элементы проверены, легче найти общие элементы двух однотипных структур, слить их воедино. Сортировка является важным средством для ускорения работы практически любого алгоритма, в котором требуется частое обращение к определенным элементам структуры данных.

Разработано множество алгоритмов сортировки, однако нет алгоритма, который был бы наилучшим в любом случае. Эффективность алгоритма сортировки может зависеть от ряда факторов, таких, как: число сортируемых элементов; степень отсортированности элементов; характеристики алгоритма (сложность, требования к памяти и т.п.); место размещения элементов (в оперативной памяти или на ВЗУ).

Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с одинаковыми ключами не изменяется. Устойчивость сортировки желательна, если речь идет об элементах, уже отсортированных по некоторым другим ключам (свойствам), не влияющим на ключ, по которому сейчас осуществляется сортировка.

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

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

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

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

Пример:

B=<20, -5, 10, 8, 7>, исходный список;

B₁=<-5, 10, 8, 7, 20>, IS=’1’ B;

B₂=<-5, 8, 7, 10, 20>, IS=’1’ B

B₂=<-5, 7, 8, 10, 20>, IS=’1’ B;

B₃=<-5, 7, 8, 10, 20>, IS=’0’ B.

В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса n до индекса m) в порядке возрастания элементов.

Нижеприведенная функция bubble сортирует входной массив методом пузырьковой сортировки.

/* сортировка пузырьковым методом */

float *bubble(float *a, intm, intn)

{

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);

}

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