Сортировка списков путем слияния

Дата добавления: 2014-12-01; просмотров: 558; Нарушение авторских прав

Для получения упорядоченного списка B' последовательность значений В=<K1,K2,...,Kn> разделяют на N списков В1=<K1>, B2=<K2>,...,Bn=<Kn>, длина каждого из которых 1. Затем осуществляется функция прохода, при которой М>=2 упорядоченных списков B1,B2,...,Bm заменяется на М/2 (или (М+1)/2) упорядоченных списков, B(2i-1)-oго и B(2i)-ого ( 2i<=M ) и добавлением Вm при нечетном М. Проход повторяется до тех пор пока не получится одна последовательность длины N.

Приведем пример сортировки списка путем использования слияния, отделяя последовательности косой чертой, а элементы запятой.

Пример:

9 / 7 / 18 / 3 / 52 / 4 / 6 / 8 / 5 / 13 / 42 / 30 / 35 / 26; 7,9 / 3,18 / 4 / 52 / 6 / 8 / 54 / 13 / 30 / 42 / 26 / 35; 3,7,9,18 / 4,6,8,52 / 5,13,30,42 / 26,35; 3,4,6,7,8,9,18,52 / 5,13,26,30,35,42; 3,4,5,6,7,8,9,13,18,26,30,35,42,52.

Количество действий, требуемое для сортировки слиянием, равно Q=N*log2(N), так как за один проход выполняется N сравнений, а всего необходимо осуществить log2(N) проходов. Сортировка слиянием является очень эффективной и часто применяется для больших N, даже при использовании внешней памяти.

Функция smerge упорядочивает массив s сортировкой слиянием, используя описанную ранее функцию merge.

/* сортировка слиянием */ double *smerge (double *s, int m, int n) { int l,low,up; double *merge (double *, int, int, int); l=1; while(l<=(n-m)) { low=m; up=m-1; while (l+up < n) { up=(low+2*l-1 < n) ? (low+2*l-1) : n ; merge (s,low,up,l); low=up-1; } l*=2; } return(a); }

Для сортировки массива путем слияния удобно использовать рекурсию. Составим рекурсивную функцию srecmg для сортировки массива либо его части. При каждом вызове сортируемый массив делится на две равных части, каждая из которых сортируется отдельно, а затем происходит их слияние, как это показано на рис.29.

Рис.29. Схема сортировки слиянием.

/* рекурсивная сортировка слиянием 1/2 */ double *srecmg (double *a, int m, int n) { double * merge (double *, int, int, int); double * smerge (double *, int, int); int i; if (n>m) { i=(n+m)/2; srecmg(a,m,i); srecmg(a,i+1,n); merge(a,m,n,(n-m)/2+1); } return (a); }

<== предыдущая лекция	\|	следующая лекция ==>
Слияние списков	\|	Быстрая и распределяющая сортировки