Стійка сортування
Матеріал з Вікіпедії - вільної енциклопедії
Поточна версія сторінки поки не перевірялася досвідченими учасниками і може значно відрізнятися від версії , перевіреної 2 липня 2011; перевірки вимагають 13 правок .
Стійка (стабільна) сортування - сортування, яка не змінює відносний порядок сортованих елементів, що мають однакові ключі. Більшість простих методів сортування стійкі, більшість складних - ні.
Стійкість є дуже важливою характеристикою алгоритму сортування, але, тим не менш, вона практично завжди може бути досягнута шляхом подовження вихідних ключів за рахунок додаткової інформації про їх первісному порядку. Незважаючи на гадану необхідність, що випливає з назви, стабільність зовсім не обов'язкова для правильності сортування і найчастіше не дотримується, так як для її забезпечення практично завжди необхідні додаткова пам'ять і час.
Зміст [убрать]
|
[ Правити ]Алгоритми стійкою сортування
Нижче наводяться описи алгоритмів стійкою сортування з часом роботи не гірше O (n log 2 n) (крім найгірших випадків в алгоритмі з використанням стійкого поділу). У всіх псевдокоду пара косих / / означає коментар до кінця рядка як у мові C + +.
[ Правити ]Сортування злиттям з додатковою пам'яттю
Основна стаття: Сортування злиттям
При цьому алгоритмі сортування спочатку здійснюється рекурсивне поділ вихідного масиву на частини до тих пір, поки в кожній частині масиву не виявиться один або нуль елементів (на кожному кроці рекурсії здійснюється поділ навпіл). Після цього отримані частини попарно «зливаються». Загальна складність алгоритму - O (n log n), при цьому алгоритму потрібно O(n) додаткової пам'яті для зберігання злитих масивів.
[ Правити ]Сортування з використанням стійкого поділу
Даний алгоритм схожий на алгоритм швидкого сортування . Так само як і в алгоритмі швидкого сортування, в даному алгоритмі вихідний масив поділяється на дві частини - в одній всі елементи менше або дорівнюють деякого опорного елементу, а в іншій - більше або рівні. Після цього розділені частини масиву рекурсивно сортуються таким же чином. Відмінність цього алгоритму від алгоритму швидкого сортування в тому, що тут використовується сталий поділ замість нестійкого. Нижче наведена реалізація даного алгоритму на псевдокоді:
Sort(a[1..n])
if(n > 1) then N ← a[ 1 ]; m ← StablePartition(a[1..n], N);
Sort(a[1..m]); Sort(a[m+1..n]); StablePartition(a[1..n], N) if( n >
1 ) then 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)); else if(a[1] < N) then return(1); else return(0)
Процедура Rotate:
Rotate(a[1..n],
m) if( n > m > 1 ) //в
массиве
хотя
бы
два
элемента
и
сдвиг
имеет
смысл
shift ← mn; //число
позиций
на
которое
будет
осуществляться
сдвиг
gcd ← GCD(m-1, n); //GCD - это
наибольший
общий
делитель
for 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;
Rotate(a[1..n], m) if( n > m > 1 ) //в массиве хотя бы два элемента и сдвиг имеет смысл shift ← mn; //число позиций на которое будет осуществляться сдвиг gcd ← GCD(m-1, n); //GCD - это наибольший общий делитель for 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 (n log n) елементарних операцій. Так як «глибина» здійснюваного рекурсивного спуску в середньому випадку становить O (log n) то загальна складність алгоритму становить O (n log ² n). При цьому алгоритму для здійснення рекурсії буде потрібно O (log n) стекової пам'яті, хоча в гіршому випадку загальна складність дорівнює O (n ² log n) і потрібно O (n) пам'яті.