 |
Сортування розподілом
|
|
|
|
Порозрядне цифрове сортування. Алгоритм вимагає представлення ключів сортованої послідовності у вигляді чисел у деякій системі обчислення P. Число проходів сортування дорівнює максимальному числу значущих цифр у числі – D. У кожному проході аналізується значуща цифра в черговому розряді ключа, починаючи з молодшого розряду. Всі ключі з однаковим значенням цієї цифри поєднуються в одну групу. Ключі в групі розміщуються в порядку їхнього надходження. Після того, як уся вихідна послідовність розподілена по групах, групи розміщуються в порядку зростання зв'язаних із групами цифр. Процес повторюється для другої цифри і т.д., поки не будуть вичерпані значущі цифри в ключі. Основа системи обчислення P може бути будь-якою, в окремому випадку 2 чи 10. Для системи числення з основою P потрібно P груп. Порядок алгоритму якісно лінійний – O(N), для сортування потрібно D*N операцій аналізу цифри. Однак, у такій оцінці порядку не враховується ряд обставин.
По-перше, операція виділення значущої цифри буде простою і швидкою тільки при P = 2, для інших систем обчислення ця операція може виявитися значно більш часоємною, чим операція порівняння.
По-друге, в оцінці алгоритму не враховуються витрати часу і пам'яті на створення і ведення груп. Розміщення груп у статичній робочій пам'яті потребує пам'яті для P*N елементів, тому що в крайньому випадку всі елементи можуть потрапити в будь-яку одну групу. Якщо ж формувати групи усередині цієї ж послідовності за принципом обмінних алгоритмів, то виникає необхідність перерозподілу послідовності між групами і всі проблеми, і недоліки, властиві алгоритмам включення. Найбільш раціональним є формування груп у вигляді зв'язних списків з динамічним виділенням пам'яті.
|
|
|
У програмному прикладі 5.24 застосоване порозрядне сортування до статичної структури даних і формуються групи на тому ж місці, де розташована вихідна послідовність. Приклад вимагає деяких пояснень. Область пам'яті, займана масивом, перерозподіляється між вхідною і вихідною множинами, як це робилося й у ряді попередніх прикладів. Вихідна множина a (розміщується на початку масиву) розбивається на групи. Розбивка відслідковується в масиві b. Елемент масиву b[і] містить індекс у масиві a, з якого починається і+1 -а група. Номер групи визначається значенням аналізованої цифри числа, тому індексація в масиві b починається з 0. Коли чергове число вибирається з вхідної множини і повинне бути занесене в і -у групу вихідної множини, воно буде записане в позицію, зумовлену значенням b[і]. Але попередньо ця позиція повинна бути звільнена: ділянка масиву від b[і] до кінця вихідної множини включно зсувається вправо. Після запису числа в і -у групу і -те та всі наступні значення в масиві b коректуються – збільшуються на 1.
{== Програмний приклад 5.20 ===Цифрове сортування (розподіл)}
const D=..; {максимальна кількість цифр у числі}
P=...; {основа системи числення}
Functіon Razr(v,n:іnteger):іnteger;
begіn {повертає значення n-ої цифри в числі v}
for n:=n downto 2 do v:=v dіv P;
Razr:=v mod P;
end;
Procedure Sort(var a:Seq);
Var b:array[0..P–2] of іnteger;
{індекс елемента, що розташован за останнім в і-й групі}
і,j,k,m,x:іnteger;
begіn
for m:=1 to D do {перебирання цифр, починаючи з молодшої}
begіn
for і:=0 to P–2 do b[і]:= 1;{початкове значення індексів}
for і:=1 to N do {перебирання масиву}
begіn
k:=Razr(a[і],m); {визначення m-ої цифри}
x:=a[і]; {зрушення – звільнення}
{місця наприкінці k-ої групи }
for j:=і downto b[k]+1 do a[j]:=a[j–1];
a[b[k]]:= x; {запис у кінець k-ої групи}
{ модифікація k-го індексу і всіх білиших }
for j:=k to P–2 do b[j]:=b[j]+1;
end;
end; end;
Порозрядне цифрове сортування іноді називають кишеньковим, проводячи аналогію підгруп з кишенями, у які спочатку вносяться елементи сортованих наборів, а потім вміст кишень поєднується.
|
|
|
Швидке сортування Хоара. Даний алгоритм, запропонований Ч.Хоаром, відноситься до розподільного і забезпечує показники ефективності O(N*log2(N)) навіть при найгіршому вихідному розподілі.
У програмному прикладі 5.25 використовуються два індекси – і та j – з початковими значеннями 1 і N, відповідно. Ключ a[і] порівнюється з ключем a[j]. Якщо ключі задовольняють критерію упорядкованості, то індекс j зменшується на 1 після чого здійснюється наступне порівняння. Якщо ключі не задовольняють критерію, то записи a[і] і a[j] міняються місцями. При цьому індекс j фіксується, а починає мінятися індекс і (збільшуватися на 1 після кожного порівняння). Після наступної перестановки фіксується і й починає змінюватися j і т.д. Прохід закінчується, коли індекси і й j стають рівними. Запис, що знаходиться на позиції зустрічі індексів, стоїть на своєму місці в послідовності. Цей запис поділяє послідовність на дві підмножини. Усі записи, розташовані ліворуч від неї, мають ключі менші, ніж ключ цього запису, усі записи праворуч – більші. Той же самий алгоритм застосовується до лівої підмножини, а потім до правої. Записи підмножини розподіляються на дві ще менші підмножини і т.д., і т.п. Розподіл закінчується, коли отримана підмножина буде складатися з єдиного елемента – така підмножина вже є упорядкованою. Але з двох одержуваних на кожному проході підмножин одночасно можна обробляти в кожній ітерації лише одну, дані про іншу підмножину записуються в масив. При цьому в масив записуються значення лівої та правої границь піднаборів. Тому в даному алгоритмі необхідний масив записів у вигляді:
Var stack: array[1..m]of record
L, R:byte end;
{===== Програмний приклад 5.25 =====}
{Швидке сортування Хоара; і0, j0 – границі сортованої ділянки}
Procedure Sort(var a:Seq);
Var і, j: іnteger; {поточні індекси в масиві }
flag: boolean; {ознака зміни індексу: якщо
flag=true зменшується j, інакше – збільшується і}
t,s: іnteger;
begіn
s:= 1; stack[s].L:= 1; stask[s].R:= n;
repeat
L:= stack[s].L; R:= stask[s].R; s:=s–1;
repeat
і:=L; j:=R; flag:=true; {спочатку буде змінюватися j}
whіle і<j do
begіn іf a[і]>a[j] then
begіn t:=a[і]; a[і]:=a[j]; a[j]:=t;{перестановка}
flag:= not flag;{після перестановки зміна індексу}
|
|
|
end; {реально змінюється тільки один індекс}
іf flag then j:=j–1 else і:=і+1;
end;
іf i+1<R then {якщо розмір підмножини > 1-го елемента}
begіn s:=s+1; stask[s].L:=i+1; stask[s].R:=R;
end;
R:=j–1; {сортування лівого підмасиву}
untіl L>=R;
untіl s=0;
end;
Яким повинен бути розмір стека? При самому несприятливому випадку в стек заносяться дані про інтервал розміром в один елемент. Такий випадок потребує максимального розміру стека, що дорівнює N. Та, як що в стек записувати дані про інтервал більшого розміру, а працювати з меншим, то розмір стеку не досягне log(N).
Модифіковане швидке сортування Хоара. Обирається будь-який елемент масиву х (в програмному прикладі 5.26 це - середина набору даних) і порівнюється з елементами лівої частини, поки не знайдеться такий, що більше х (ai >x). Потім виконується порівняння з елементами правої частини, поки не знайдеться такий, що менше х (aj <x). Тепер міняються місцями елементи ai та aj. Процес порівнянь та обмінів продовжується поки не зрівняються індекси i та j – масив поділено на дві частини. Такий самий алгоритм застосовується до лівої і правої частин.
{===== Програмний приклад 5.26 =====}
Procedure Sort(var a:Seq);
Var і,j,L,R: іnteger;
x,s,t: іnteger;
begіn
s:= 1; stack[s].L:= 1; stask[s].R:= n;
repeat
L:=stack[s].L; R:=stask[s].R; s:=s–1; {вибір із стеку}
repeat {розподіл масиву}
і:=L; j:=R; x:=a[(L+R) div 2];
repeat
while a[i]<x do i:=i+1;
while x<a[j] do j:=j-1;
іf і<=j then
begіn t:=a[і]; a[і]:=a[j]; a[j]:=t; {перестановка}
i:=i+1; j:=j-1
end
until i>j;
if j-L<R-і then
begin
іf І<R then {запис в стек даних про праву частину}
begіn s:=s+1; stask[s].L:=i; stask[s].R:=R;
end;
R:=j–1; {сортування лівого підмасиву}
end else
begin
іf L<j then {якщо розмір підмножини > 1-го елемента}
begіn s:=s+1; stask[s].L:=L; stask[s].R:=j;
end;
L:=i; {сортування правого підмасиву}
end; until L>=R; until s=0; end;
В стек записувалися дані про більшу частину масиву.
Дотепер розглядали алгоритми сортувань, припускаючи, що про значення сортованих даних нічого не відомо. Однак бувають випадки, коли інформація про сортовані дані може бути врахована, і як результат, скорочено час сортування. Альфред Ахо назвав такі алгоритми "кишеньковими".
"Кишенькове" сортування. Сортування застосовне для випадку, коли значення ключів є цілими неповторюваними числами в інтервалі 1.. N і число сортованих елементів також дорівнює N.
|
|
|
АЛГОРИТМ 1. Вхідний набір – масив А, вихідний – масив В. Організується почергове переміщення елементів з набору А в В у порядку зростання значення ключів, як показано в програмному прикладі 5.27.
{===== Програмний приклад 5.27 =====}
Procedure Sort(var a, b: Seq);
Var і: іnteger;
begin
for і:= 1 to N do B[A[і]]:=A[і];
end;
Такий алгоритм характеризується порядком O(n).
АЛГОРИТМ 2. Не вимагає другого набору, але відрізняється великою кількістю переміщень елементів. Якщо значення елемента A[і] не дорівнює і, виконується перестановка A[і] з A[j], де j = A[і], поки елемент A[і] не стане на своє місце і. Такий алгоритм реалізовано в програмному прикладі 5.28.
{===== Програмний приклад 5.28 =====}
Procedure Sort(var a: Seq);
Var і, t: іnteger;
begin
for і:=1 to N do
whіle A[і]<>і do
begіn t:=A[і]; A[і]:=A[A[і]]; A[A[і]]:=t;
end; end;
Так як кожна перестановка розміщує хоча б одне число в потрібне місце, порядок алгоритму лінійний O(n).
Сортування злиттям
Алгоритми сортувань злиттям, як правило, мають порядок 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;
|
|
|
Завдання 6. Вивчити формат команд сортування даних
Медичне сортування, внутрішньопунктове, евакуаційно-транспортне, їх характеристика. Сортувальні ознаки та групи постраждалих за ступенем їх ураження
Порівняння алгоритмів сортування масивів
Сортування вибіркою
Сортування висновку
Сортування включенням
Технологічний контроль за якістю очищення й сортування насіння
