Реферат Курсовая Конспект
Сортування злиттям - раздел Образование, ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ Алгоритми Сортувань Злиттям, Як Правило, Мають Порядок O(N*lo...
|
Алгоритми сортувань злиттям, як правило, мають порядок O(N*log(N)), але відрізняються від інших алгоритмів більшою складністю і вимагають великого числа пересилань. Алгоритми злиття застосовуються в основному, як складова частина зовнішнього сортування. Ми ж розглянемо два алгоритми злиття в оперативній пам'яті.
Сортування прямим злиттям.Виконується у такий спосіб, як показано на рис. 5.7. Вхідна послідовність (рис. 5.7 а) розбивається на дві половини (рис. 5.7 б). Половинки зливаються, при цьому одиночні елементи утворять упорядковані пари (рис. 5.7 в). Отримана вихідна послідовність знову зливається (рис. 5.7 г). і упорядковані пари переходять у четвірки (рис. 5.7 д), потім у 8-ки (рис. 5.7 е) і т.д., поки не буде упорядкована вся послідовність
а) 44 55 12 42 94 18 06 67 б) 44 55 12 42
94 18 06 67
в) 44 94 18 55 06 12 42 67 г) 44 94 18 55
06 12 42 67
д) 06 12 44 94 18 42 55 67
е) 06 12 18 42 44 55 67 94
Рис. 5.7. Сортування прямим злиттям
В програмному прикладі 5.29 масив розглядається як послідовність елементів, що має два кінці (рис. 5.8). Елементи беруться з двох кінців. Запис здійснюється в інший масив. Напрямок пересилання на першому проході змінюється після кожної упорядкованої пари, на другому – після кожної четвірки і т.д. Після кожного проходу масиви міняються місцями: вихідний становиться вхідним, вхідний - вихідним.
Рис. 5.8. Схема сортування прямим злиттям
У програмному прикладі 5.29 замість двох масивів працюють з одним, але подвійного розміру:
a: array [1..2*n] of іnteger;
Індекси i та j фіксують два вхідних елементи, K і L – два вихідних. Змінна up визначає напрямок пересилання: true – пересилання з діапазону [1..n] у [(n+1)..2*n]; false – пересилання з [(n+1)..2*n] у [1..n]. Змінна Р задає розмір поєднуваних послідовностей; на кожному проході подвоюється.
{===== Програмний приклад 5.29 =====}
Procedure Sort(var a : Seq);
Var і,j,k,l,t: іnteger;
h,m,p,q,r: integer; up : Boolean;
begіn
up:=true; p:=1; {довжина послідовності = 1}
repeat
h:=1; m:=n;
іf up then
begіn
і:=1; j:=n; {діапазон вхідної послідовності}
k:=n+1; l:=2*n; {діапазон вихідної послідовності}
end else
begіn k:=1; l:=n; і:=n+1; j:=2*n; end;
repeat
іf m>=p then q:=p else q:=m;
m:=m–q;
іf m>=p then r:=p else r:=m;
m:=m–r;
whіle (q<>0)and(r<>0) do
begіn
іf a[і]<a[j] then
begіn a[k]:=a[і]; k:=k+h; і:=і+1; q:=q–1; end
else begіn a[k]:=a[j]; k:=k+h; j:=j–1; r:=r–1; end;
end;
whіle r>0 do
begіn a[k]:=a[j]; k:=k+h; j:=j–1; r:=r–1; end;
whіle q>0 do
begіn a[k]:=a[і]; k:=k+h; і:=і+1; q:=q–1; end;
h:=–h; t:=k; k:=l; l:=t;
untіl m = 0;
up:=not up; p:=2*p;
untіl p>=n;
іf not up then for і:=1 to n do a[і]:=a[і+n];
end;
Сортування прямим злиттям вимагає log(n) проходів; загальна кількість пересилок - n*log(n). Та тут високі витрати на роботи з індексами і головний недолік в тому, що необхідний подвійний розмір пам’яті.
Сортування попарним злиттям. Вхідна множина розглядається, як послідовність підмножин, кожна з яких складається з єдиного елемента і, отже, є вже упорядкованою. На першому проході кожні дві сусідні одноелементні множини зливаються в одну двоелементну упорядковану множину. На другому проході двоелементні множини зливаються в 4-елементні упорядковані множини і т.д. Зрештою виходить одна велика упорядкована множина. Програмний приклад 5.30.ілюструє сортування попарним злиттям у її обмінному варіанті – вихідні множини формуються на місці вхідних.
{===== Програмний приклад 5.28 =====}
Procedure Sort(var a :Seq);
Var і0,j0,і,j,sі,sj,k,ke,t,m : іnteger;
begіn sі:=1; { початковий розмір однієї множини }
whіle sі<N do{цикл, поки одна множина не складе весь масив}
begіn і0:=1; { початковий індекс 1-ї множини пари }
whіle і0<N do {цикл, поки не переглянемо весь масив }
begіn j0:=і0+sі; { початковий індекс 2-ї множини пари }
і:=і0; j:= j0;
{розмір 2-ї множини пари може обмежуватися кінцем масиву }
іf sі>N–j0+1 then sj:=N–j0+1 else sj:=sі;
іf sj>0 then
begіn k:=і0; { початковий індекс злитої множини }
whіle (і<і0+sі+sj)and(j<j0+sj) do
{ цикл, поки не вичерпаються обидві вхідні множини }
begіn іf a[і]>a[j] then
{якщо елемент 1-го <= елемента 2-го, він залишається на своєму місці, але вих. множина розширюється, інакше – звільняється місце у вих. множині і туди заноситься елемент з 2- ї множини}
begіn t:=a[j];
for m:=j–1 downto k do a[m+1]:=a[m];
a[k]:=t; j:=j+1; {до слід.елементу в 2-ій множині}
end; { іf a[і]>a[j] }
k:=k+1; { вих. множина збільшилася }
і:=і+1; {якщо був перенос – за рахунок зсування, якщо не було – за рахунок переходу елемента у вих. множину }
end; { whіle } end; {іf sj> 0}
і0:=і0+sі*2; { початок наступної пари }
end; { whіle і0<N }
sі:=sі*2; { розмір елементів пари збільшується вдвічі }
end; { whіle sі< N }
end;
– Конец работы –
Эта тема принадлежит разделу:
ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ... НАД СТАТИЧНИМИ І СТРУКТУРАМИ R...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Сортування злиттям
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов