[ Правити ]Алгоритми сортування злиттям без додаткової пам'яті

Всі описані нижче алгоритми засновані на злитті вже відсортованих масивів без використання додаткової пам'яті понад O (log ² n) стекової пам'яті (це - т. зв. Умова мінімальної пам'яті ^[1]) і відрізняються лише алгоритмом злиття. Далі наведено псевдокод алгоритмів (алгоритми злиття - процедура Merge - наводяться окремо для кожного методу):

Sort(a[1..n]) if( n > 1 ) then m← n/2 ; Sort(a[1..m]); Sort(a[m+1..n]); Merge(a[1..n], m);

Sort(a[1..n]) if( n > 1 ) then m← n/2 ; Sort(a[1..m]); Sort(a[m+1..n]); Merge(a[1..n], m);

[ Правити ]Алгоритм Пратта

В алгоритмі Пратта в відсортованих масивах знаходять два елементи α і β, які є медианами масиву, що складається з елементів обох масивів. Тоді весь масив можна представити у вигляді aαbxβy. Після цього здійснюється циклічний зсув елементів в результаті чого отримуємо таку послідовність: axβαby. Далі алгоритм злиття рекурсивно повторяться для масивів ax і by.

Merge(a[1..n], m) if(m <> 1 and m <> n) //это условие означает, что в массиве должно быть хотя бы 2 элемента if( n-1 > 2 ) //случай, когда элементов ровно два, приходится рассматривать отдельно if( m-1 > nm ) leftBound←1; rightBound←m; while( leftBound < rightBound ) do //в этом цикле ищем медианы m1 ← (leftBound+rightBound)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); //реализация процедуры FindFirstPosition см. след. пункт if( m1 + (m2-m) > n/2 ) then rightBound ← m1-1; else leftBound ← m1+1; Rotate(a[m1..m2], m); Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2); else if(a[m] < a[1]) a[m] a[1];

Merge(a[1..n], m) if(m <> 1 and m <> n) //это условие означает, что в массиве должно быть хотя бы 2 элемента if( n-1 > 2 ) //случай, когда элементов ровно два, приходится рассматривать отдельно if( m-1 > nm ) leftBound←1; rightBound←m; while( leftBound < rightBound ) do //в этом цикле ищем медианы m1 ← (leftBound+rightBound)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); //реализация процедуры FindFirstPosition см. след. пункт if( m1 + (m2-m) > n/2 ) then rightBound ← m1-1; else leftBound ← m1+1; Rotate(a[m1..m2], m); Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2); else if(a[m] < a[1]) a[m] a[1];

Циклічний зсув елементів вимагає O (n) елементарних операцій і O (1) додаткової пам'яті, а пошук медиан в двох вже відсортованих масивах - O (log ² n) елементарних операцій і O (1) додаткової пам'яті. Так як здійснюється O (log n) кроків рекурсії, то складність такого алгоритму злиття становить O (n log n), а загальна складність алгоритму сортування - O (n log ² n).При цьому алгоритму потрібно O (log ² n) стекової пам'яті.

[ Правити ]Алгоритм без пошуку медиан

Від пошуку медиан в попередньому алгоритмі можна позбутися в такий спосіб. В більшому з двох масивів вибираємо середній елемент α (опорний елемент). Далі в меншому масиві знаходимо позицію першого входження елемента більшого чи рівного α. Назвемо його β. Після цього здійснюється циклічний зсув елементів так само як і в алгоритмі Пратта (aαbxβy →axβαby) і здійснюється рекурсивне злиття отриманих частин. Псевдокод алгоритму злиття наведено нижче.

Merge(a[1..n], m) if(m <> 1 and m <> n) //это условие означает что в массиве должно быть хотя бы 2 элемента if( n-1 > 2 ) //случай когда элементов ровно два приходится рассматривать отдельно if( m-1 > nm ) m1 < (m+1)/2 ; m2 < FindFirstPosition(a[m..n], a[ m1 ]); else m2 < (n+m)/2 ; m1 < FindLastPosition(a[1..m], a[ m2 ]); Rotate(a[m1..m2], m); Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2); else if(a[ m ] < a[ 1 ]) a[ m ] a[ 1 ];

Merge(a[1..n], m) if(m <> 1 and m <> n) //это условие означает что в массиве должно быть хотя бы 2 элемента if( n-1 > 2 ) //случай когда элементов ровно два приходится рассматривать отдельно if( m-1 > nm ) m1 < (m+1)/2 ; m2 < FindFirstPosition(a[m..n], a[ m1 ]); else m2 < (n+m)/2 ; m1 < FindLastPosition(a[1..m], a[ m2 ]); Rotate(a[m1..m2], m); Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2); else if(a[ m ] < a[ 1 ]) a[ m ] a[ 1 ];

Процедури FindFirstPosition і FindLastPosition практично збігаються з процедурою двійкового пошуку:

FindFirstPosition(a[1..n], x) leftBound < 1; rightBound < n; current < 1; while(leftBound < rightBound) do current < [(leftBound+rightBound)/2]; if(a[ current ] < x) then leftBound < current+1 else rightBound < current; return(current); FindLastPosition(a[1..n], x) leftBound < 1; rightBound < n; current < 1; while(leftBound < rightBound) do current < [(leftBound+rightBound)/2]; if( x < a[ current ] ) then rightBound < current; else leftBound < current+1 return(current);

FindFirstPosition(a[1..n], x) leftBound < 1; rightBound < n; current < 1; while(leftBound < rightBound) do current < [(leftBound+rightBound)/2]; if(a[ current ] < x) then leftBound < current+1 else rightBound < current; return(current); FindLastPosition(a[1..n], x) leftBound < 1; rightBound < n; current < 1; while(leftBound < rightBound) do current < [(leftBound+rightBound)/2]; if( x < a[ current ] ) then rightBound < current; else leftBound < current+1 return(current);

На відміну від алгоритму Пратта в даному алгоритмі розбиття може бути істотно нерівним. Але навіть у гіршому випадку алгоритм розіб'є весь діапазон [a .. y] в співвідношенні 3:1 (якщо все елементи другого діапазону будуть більше або менше опорного і при цьому обидва діапазону мають рівне число елементів). Це гарантує логарифмічне число кроків рекурсії при злитті будь-яких масивів. Таким чином отримуємо, що так само, як і в алгоритмі Пратта, складність алгоритму злиття дорівнює O (n log n), складність алгоритму сортування - O (n log ² n), а необхідна пам'ять - O (log ² n).