Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Сортировка слиянием. Этот метод сортирует массив последовательным слиянием пар уже отсортированных подмассивов, поэтому его и назвали сортировкой слиянием.
|
|
Этот метод сортирует массив последовательным слиянием пар уже отсортированных подмассивов, поэтому его и назвали сортировкой слиянием.
Пусть k - положительное целое число. Разобьем массив A[1]..A[n] на отрезки длины k. (Первый - A[1]..A[k], затем A[k+1]..A[2k] и т.д.) Последний отрезок будет неполным, если n не делится нацело на k. Назовем массив k-упорядоченным, если каждый из этих отрезков длины k упорядочен.
Ясно, что любой массив 1-упорядочен, так как его подмассивы длиной 1 можно считать упорядоченными. Если массив k-упорядочен и n< =k, то он упорядочен.
Теперь запишем общую схему алгоритма:
k: =1; while k < n dobegin... преобразовать k-упорядоченный массив в 2k-упорядоченный; k: = 2 * k; end;Рассмотрим процедуру преобразования k-упорядоченного массива в 2k-упорядоченный. Сгруппируем все подмассивы длины k в пары подмассивов. Теперь пару упорядоченных подмассивов сольем в один упорядоченный подмассив. Проделав это со всеми парами, мы получим 2k-упорядоченный массив:
t: =0; while t + k < n dobegin p: = t; q: = t+k;...r: = min(t+2*k, n); {в паскале нет функции min }...сливаем два подмассива A[p..q-1] и A[q..r] t: = r; end;Слияние требует вспомогательного массива для записи результатов слияния - обозначим его B. Через p0 и q0 обозначим номера последних элементов участков, подвергшихся слиянию, s0 - последний записанный в массив B элемент. На каждом шаге слияния производится одно из двух действий:
B[s0+1]: =A[p0+1];
Inc(p0); Inc(s0);или
B[s0+1]: =A[q0+1]; Inc(q0); Inc(s0);Первое действие (взятие элемента из первого отрезка) может производиться при двух условиях:
(1) первый отрезок не кончился (p0 < q);
(2) второй отрезок кончился (q0 = r) или не кончился, но элемент в нем не меньше [(q0 < r) и (A[p0+1] < = A[q0+1])].
Аналогично для второго действия. Итак, получаем
p0: = p; q0: = q; s0: = p; while (p0< > q)or(q0< > r) dobegin if (p0< q)and((q0=r)or((q0 < r) and (A[p0+1]< =A[q0+1]))) then begin B[s0+1]: = A[p0+1]; Inc(p0); Inc(s0); end else begin B[s0+1]: = A[q0+1]; Inc(q0); Inc(s0); end; end;(Если оба отрезка не кончены и первые невыбранные элементы в них равны, то допустимы оба действия; в программе выбрано первое.)
Осталось собрать программу в одно целое:
k: = 1; while k < N dobegin t: = 0; while t+k < N do begin p: = t; q: = t+k; if t+2*k> N then r: = N else r: = t+2*k; p0: = p; q0: = q; s0: = p; while (p0< > q) or (q0< > r) do begin if (p0< q) and ((q0=r)or((q0< r)and (A[p0+1]< =A[q0+1]))) then begin B[s0+1]: = A[p0+1]; Inc(p0); end else begin B[s0+1]: = A[q0+1]; Inc(q0); end; Inc(s0); end; t: = r; end; k: = k shl 1; A: = B; end;Сразу же бросается в глаза недостаток метода – он требует дополнительную память размером порядка N (для хранения вспомогательного массива). Но как и для древесной сортировки, его временная сложность всегда пропорциональна N*log(N) (так как преобразование k-упорядоченного массива в 2k-упорядоченный требует порядка N действий и внешний цикл по k совершает порядка log(N) итераций).
|
|