Stabilní řazení

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. ledna 2020; kontroly vyžadují 2 úpravy .

Stabilní (stabilní) řazení  - řazení , které nemění relativní pořadí seřazených prvků, které mají stejné klíče, podle kterých k řazení dochází.

Stabilita je velmi důležitou vlastností třídícího algoritmu, ale přesto jí lze téměř vždy dosáhnout prodloužením původních klíčů o další informace o jejich původním pořadí. Navzdory zřejmé nutnosti naznačené z názvu není stabilita pro správné řazení vůbec nutná a většinou se nedodržuje, protože k jejímu zajištění je téměř vždy zapotřebí další paměť a čas.

Příklad

Při řazení záznamů ve tvaru [příjmení, jméno, patronymie] podle příjmení budou klíčové hodnoty pro Ivanov Sergey a Ivanov Ivan stejné, takže stabilní řazení nezamění Sergeje a Ivana ( Python 3 , timsort sort [1] ):

záznamy = [ { 'příjmení' : 'Ivanov' , 'křestní jméno' : 'Sergey' , 'patronymic' : 'Michajlovič' ,}, { 'příjmení' : 'Ivanov' , 'křestní jméno' : 'Ivan' , ' patronymic' : 'Borisovich' ,}, { 'příjmení' : 'Abramov' , 'křestní jméno' : 'Yuri' , 'patronymic' : 'Petrovich' ,}, ] záznamy . řazení ( klíč = lambda x : x [ 'příjmení' ]) # řazení podle klíče "příjmení" pro r v záznamech : tisk ( ' %-12s %-12s %-12s ' % ( r [ 'příjmení' ] , r [ 'křestní jméno' ], r [ 'patronymické' ]))

V důsledku toho budou záznamy seřazeny pouze podle příjmení, přičemž bude zachováno původní pořadí mezi záznamy se stejným příjmením:

Abramov Jurij Petrovič Ivanov Sergej Michajlovič Ivanov Ivan Borisovič

Aplikace

Třídění, které je hlavním nákladovým prvkem Burroughs-Wheelerovy transformace , musí být robustní.

Algoritmy Stablesort

Níže jsou uvedeny popisy robustních třídicích algoritmů s dobou běhu ne horší než O( n log 2 n ) (kromě nejhorších případů v algoritmu používajícím stabilní dělení). Ve všech pseudokódech dvojice lomítek // znamená komentář na konec řádku, jako v C++.

Sloučit řazení s extra pamětí

S tímto třídícím algoritmem je počáteční pole nejprve rekurzivně rozděleno na části, dokud každá část pole neobsahuje jeden nebo nula prvků (půlení se provádí v každém kroku rekurze). Poté se výsledné části v párech "sloučí". Celková složitost algoritmu je O( n log n ) a algoritmus vyžaduje O( n ) extra paměť pro uložení sloučených polí.

Řazení pomocí stabilního rozdělení

Tento algoritmus je podobný algoritmu rychlého třídění . Stejně jako v algoritmu quicksort je v tomto algoritmu počáteční pole rozděleno na dvě části - v jedné jsou všechny prvky menší nebo rovny některému pivotovému prvku a ve druhé jsou větší nebo rovny. Poté jsou oddělené části pole rekurzivně seřazeny stejným způsobem. Rozdíl mezi tímto algoritmem a algoritmem rychlého třídění je v tom, že používá stabilní oddíl namísto nestabilního. Níže je implementace tohoto algoritmu v pseudokódu:

Seřadit(a[1..n]) if(n > 1) then N ← a[ 1 ]; m ← StablePartition(a[1..n], N); Seřadit(a[1..m]); Seřadit(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); návrat (m1 + (m2-m)); jiný if(a[1] < N) then return(1); jiný vrátit (0)

Postup otáčení:

Otočit(a[1..n], m) if( n > m > 1 ) //pole má alespoň dva prvky a posun dává smysl posun ← mn; //počet pozic, které mají být posunuty gcd ← GCD(m-1, n); //GCD je největší společný dělitel pro i ← 0 až gcd-1 do hlava ← i+1; headVal ← a[hlava]; proud ← hlava; další ← hlava+posun; while(next ≠ head) dělat a[aktuální] ← a[další]; aktuální ← další; další ← další+posun; if(další>n) další ← další-n; a[aktuální] ← headVal;

K udržitelnému rozdělení pole je zapotřebí O( n log n ) základních operací . Protože „hloubka“ rekurzivního sestupu je v průměru O(log n ), celková složitost algoritmu je O( n žurnál² n ). V tomto případě bude algoritmus vyžadovat O(log n ) zásobníkovou paměť k provedení rekurze, i když v nejhorším případě je celková složitost O( n ² log n ) a vyžaduje se paměť O( n ).

Sloučit třídicí algoritmy bez další paměti

Všechny níže popsané algoritmy jsou založeny na slučování již roztříděných polí bez použití další paměti nad O(log² n ) zásobníkové paměti (toto je tzv. podmínka minimální paměti [2] ) a liší se pouze algoritmem slučování. Následuje pseudokód algoritmů (slučovací algoritmy – procedura Merge – jsou uvedeny samostatně pro každou metodu):

Seřadit(a[1..n]) if( n > 1) then m ← n/2; Seřadit(a[1..m]); Seřadit(a[m+1..n]); Sloučit(a[1..n], m); Prattův algoritmus

V Prattově algoritmu se dva prvky α a β nacházejí v seřazených polích , což jsou mediány pole sestávajícího z prvků obou polí. Celé pole pak může být reprezentováno jako aαbxβy . Poté se provede cyklický posun prvků, v důsledku čehož získáme následující sekvenci: axβαby . Dále bude slučovací algoritmus rekurzivně opakován pro pole ax a by.

Sloučit(a[1..n], m) if(m ≠ 1 a m ≠ n) //tato podmínka znamená, že pole musí mít alespoň 2 prvky if( n-1 > 2 ) //případ, kdy existují právě dva prvky, je třeba posuzovat samostatně if ( m-1 > nm ) leftBound←1; pravá hranice←m; while( leftBound < rightBound ) proveďte //hledejte mediány v této smyčce m1 ← (leftBound+rightBound)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); //implementace procedury FindFirstPosition viz dále. odstavec if( m1 + (m2-m) > n/2 ) pak pravá vazba ← m1-1; jiný levá vazba ← m1+1; Rotate(a[m1..m2], m); Sloučit(a[1..m1+(m2-m)], m1); Sloučit(a[m1+(m2-m)+1..n], m2); jiný if(a[m] < a[1]) a[m]⟷a[1];

Posouvání prvků vyžaduje O( n ) operací s prvky a O(1) další paměť, zatímco nalezení mediánů ve dvou již seřazených polích vyžaduje O(log² n ) operací s prvky a O(1) další paměť. Protože existuje O(log n ) rekurzních kroků, složitost takového slučovacího algoritmu je O( n log n ) a celková složitost třídícího algoritmu je O( n log² n ). V tomto případě bude algoritmus vyžadovat paměť zásobníku O(log² n ).

Algoritmus bez hledání mediánů

Hledání mediánů v předchozím algoritmu se můžete zbavit následovně. Ve větším ze dvou polí vyberte prostřední prvek α (hlavní prvek). Dále v menším poli najděte polohu prvního výskytu prvku většího nebo rovného α. Říkejme tomu β. Poté se prvky cyklicky posouvají jako v Prattově algoritmu ( aαbxβy → axβαby ) a získané části se rekurzivně spojují. Pseudokód slučovacího algoritmu je uveden níže.

Sloučit(a[1..n], m) if(m ≠ 1 a m ≠ n) //tato podmínka znamená, že pole musí mít alespoň 2 prvky if( n-1 > 2 ) //případ, kdy je třeba uvažovat odděleně právě dva prvky if ( m-1 > nm ) m1 ← (m+1)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); jiný m2 ← (n+m)/2 ; m1 ← FindLastPosition(a[1..m], a[ m2 ]); Rotate(a[m1..m2], m); Sloučit(a[1..m1+(m2-m)], m1); Sloučit(a[m1+(m2-m)+1..n], m2); jiný if(a[ m ] < a[ 1 ]) a[m]⟷a[1];

Procedury FindFirstPosition a FindLastPosition jsou téměř totožné s procedurou binárního vyhledávání:

FindFirstPosition(a[1..n], x) levá vazba ← 1; pravá hranice ← n; proud ← 1; while(leftBound < rightBound) do aktuální ← ⌊(levá hranice+pravá hranice)/2⌋; if(a[ aktuální ] < x) then leftBound ← aktuální+1 jiný rightBound ← aktuální; return(aktuální); FindLastPosition(a[1..n], x) levá vazba ← 1; pravá hranice ← n; proud ← 1; while(leftBound < rightBound) do aktuální ← ⌊(levá hranice+pravá hranice)/2⌋; if( x < a[ aktuální ] ) then rightBound ← aktuální; jiný leftBound ← aktuální+1 return(aktuální);

Na rozdíl od Prattova algoritmu může být v tomto algoritmu rozdělení v podstatě nerovnoměrné. Ale i v nejhorším případě algoritmus rozdělí celý rozsah [ a .. y ] v poměru 3:1 (pokud jsou všechny prvky druhého rozsahu větší nebo menší než referenční a oba rozsahy mají stejný počet prvků). To zaručuje logaritmický počet kroků rekurze při slučování libovolných polí. Dostaneme tedy, že stejně jako v Prattově algoritmu je složitost slučovacího algoritmu O( n log n ), složitost třídícího algoritmu je O( n log² n ) a požadovaná paměť je O (log² n ).

Stabilní řazení bez další paměti v čase O( n log n )

Způsoby, jak zlepšit algoritmy

  • Ve všech výše uvedených algoritmech lze při rozdělování původního pole na části zastavit rekurzivní dělení, pokud se velikost rozdělovacího pole dostatečně zmenší. Pak lze použít libovolný z jednoduchých třídicích algoritmů (např . insertion sort ), o kterých je známo, že jsou rychlejší než ty složité, pokud je velikost vstupního pole malá. Ve skutečnosti je tato technika použitelná nejen pro zde uvedené algoritmy, ale také pro jakýkoli jiný algoritmus, který používá rekurzivní dělení původního pole (například obvyklé nestabilní rychlé řazení ). Konkrétní počet vstupních prvků, při kterých je nutné přejít na jednoduchý třídicí algoritmus, závisí na použitém počítači.
  • V Prattově algoritmu, nemediánovém algoritmu a robustním algoritmu oddílu můžete místo volání sloučení pokaždé rekurzivně alokovat pole dočasných proměnných. Poté bude možné pokračovat v dělení rozsahu pouze do té doby, než počet prvků ve větším rozsahu bude menší nebo roven kapacitě dočasného pole. Ve skutečnosti se v určitém kroku rekurze Prattův algoritmus a algoritmus bez hledání mediánů promění v jednoduchý slučovací algoritmus. Že. má-li systém dostatek dynamické paměti, pak lze asymptotický čas běhu přivést na O( n log n ) místo O( n log² n ).

Poznámky

  1. ↑ Tim Sort, c2.com . Získáno 18. listopadu 2012. Archivováno z originálu 14. června 2013.
  2. ↑ Knut D., Umění programování. v. 3, Třídění a vyhledávání, M., Williams, 2000
 Algoritmy řazení
Teorie Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna
Výběr
vložky
fúze
Žádné srovnání
hybridní
jiný
nepraktický