Реферат Стійке сортування
Стійке (стабільне) сортування— сортування, яке не змінює відносний порядок сортованих елементів, що мають однакові ключі. Більшість простих методів сортування є стійкими, більшість складних — ні.
Стійкість є дуже важливою характеристикою алгоритму сортування, проте вона практично завжди може бути досягнута шляхом подовження вихідних ключів за рахунок додаткової інформації про їх початковий порядок. Незважаючи на необхідність, що випливає з назви, стабільність зовсім не обов'язкова для правильності сортування і найчастіше не дотримується, так як для її забезпечення практично завжди необхідні додаткова пам'ять і час.
1. Алгоритми стійкого сортування
1.1. Сортування злиття з додатковою пам'яттю
У цьому алгоритмі сортування спочатку здійснюється рекурсивне поділ вихідного масиву частини до тих пір, поки кожної частини масиву не виявиться чи нуль елементів (на кожному кроці рекурсії здійснюється поділ навпіл). Після цього отримані частини попарно зливаються. Загальна складність алгоритму - O(nlogn), при цьому алгоритму потрібно O(n) додаткової пам'яті для зберігання злитих масивів.
1.2. Сортування з використанням сталого поділу
Цей алгоритм схожий на алгоритм швидкого сортування. Так само як і в алгоритмі швидкого сортування, в даному алгоритмі вихідний масив поділяється на дві частини - в одній усі елементи менші або дорівнюють деякому опорному елементу, а в іншій - більші або рівні. Після цього розділені частини масиву рекурсивно сортуються так само. Відмінність цього алгоритму від алгоритму швидкого сортування в тому, що тут використовується стійкеподіл замість нестійкого. Нижче наведено реалізацію даного алгоритму на псевдокоді:
N ← a[1]; m ← StablePartition(a[1..n], N); Sort(a[1..m]); Sort(a[m+1..n]);
m ← n/2; m1 ← StablePartition(a[1..m], N); m2 ← m+StablePartition(a[m+1..n], N); Rotate(a[m1..m2], m); return(m1 + (m2-m));
if(a[1] return(1); else return(0)
if(n>m>1) //в масиві хоча б два елементи і зсув має сенс
shift ← m-n; //число позицій, на яке буде здійснюватися зсув gcd ← GCD(m-1, n); //GCD - це найбільший спільний дільник для i ← 0 to gcd-1 do head ← i+1; headVal ← a[head]; current ← head; next ← head+shift; while(next head) do a[current] ← a[next]; current ← next; next ← next+shift; if(next>n) next ← next-n; a[current] ← headVal;
Для стійкого поділу масиву потрібно O(nlogn) елементарних операцій. Оскільки «глибина» рекурсивного спуску в середньому випадку становить O(logn) то загальна складність алгоритму становить O(nlog²n). При цьому алгоритму для здійснення рекурсії буде потрібно O(logn) стекової пам'яті, хоча в гіршому випадку загальна складність дорівнює O(n² logn) і потрібно O (n) пам'яті.
1.3. Алгоритми сортування злиттям без додаткової пам'яті
Всі описані нижче алгоритми засновані на злитті вже відсортованих масивів без використання додаткової пам'яті понад O(log²n) стікової пам'яті (це - т. зв умова мінімальної пам'яті [1] ) і відрізняються лише алгоритмом злиття. Далі наведено псевдокод алгоритмів (алгоритми злиття – процедура Merge – наводяться окремо для кожного методу):
1.3.1. Алгоритм Пратта
В алгоритмі Пратта у відсортованих масивах знаходять два елементиαтаβ, які є медіанами масиву, що складається з елементів обох масивів. Тоді весь масив можна подати у виглядіaαbxβy. Після цього здійснюється циклічний зсув елементів внаслідок чого отримуємо таку послідовність:axβαby. Далі алгоритм злиття рекурсивно повториться для масивів ax і by.
if(m 1 and m n) //це умова означає, що у масиві має бути хоча б 2 елемента
if( n-1 > 2 ) //випадок, коли елементів рівно два, доводиться розглядати окремо if( m-1 > n-m ) leftBound←1; rightBound←m; while( leftBound m1 ← ; m2 ← FindFirstPosition(a[m..n], a[ m1 ])); //реалізація процедури FindFirstPosition див. далі if( m1 + (m2-m) rightBound ← m1-1, else leftBound ← m1+1, Rotate(a[m1..m2], m); m2-m)+1..n], m2), else if(a[m]a[m]a[1];
Циклічний зсув елементів вимагає O(n) елементарних операцій та O(1) додаткової пам'яті, а пошук медіан у двох вже відсортованих масивах - O(log²n) елементарних операцій та O(1 ) додаткової пам'яті. Оскільки здійснюється O(logn) кроків рекурсії, то складність такого алгоритму злиття становить O(nlogn), а загальна складність алгоритму сортування - O(nlog²n). При цьому алгоритму буде потрібно O(log²n) стекової пам'яті.
1.3.2. Алгоритм без пошуку медіан
Пошук медіан у попередньому алгоритмі можна позбутися наступним чином. У більшому з двох масивів вибираємо середній елемент (опорний елемент). Далі в меншому масиві знаходимо позицію першого входження елемента більшого або α. Назвемо його? Після цього здійснюється циклічне зрушення елементів так само як і в алгоритмі Пратта(aαbxβy→axβαby) і здійснюється рекурсивне злиття отриманих частин. Псевдокод алгоритму злиття наведено нижче.
if(m 1 and m n) //це умова означає що у масиві має бути хоча б 2 елемента
if( n-1 > 2 ) //випадок коли елементів рівно два доводиться розглядати окремо if( m-1 > n-m ) m1 ← ; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); else m2 ←; 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[m]a[1];
Процедури FindFirstPosition та FindLastPosition практично збігаються з процедурою двійкового пошуку:
current ← ; if(a[ current ] leftBound ← current+1 else rightBound ← current;
current ← ; if( x rightBound ← current; else leftBound ← current+1
На відміну від алгоритму Пратта в даному алгоритмі розбиття може бути суттєво нерівним. Але навіть у гіршому випадку алгоритм розіб'є весь діапазон [a..y] у співвідношенні 3:1 (якщо всі елементи другого діапазону будуть більшими або меншими за опорний і при цьому обидва діапазони мають рівне кількість елементів). Це гарантує логарифмічну кількість кроків рекурсії при злитті будь-яких масивів. Таким чином отримуємо, що так само, як і в алгоритмі Пратта, складність алгоритму злиття дорівнює O(nlogn), складність алгоритму сортування - O(nlog²n), а необхідна пам'ять - O(log²n).