Stabil (stabil) rendezés - rendezés , amely nem változtatja meg az azonos kulcsokkal rendelkező rendezett elemek egymáshoz viszonyított sorrendjét, amely alapján a rendezés megtörténik.
A stabilitás nagyon fontos jellemzője egy rendezési algoritmusnak, de ennek ellenére szinte mindig elérhető az eredeti kulcsok meghosszabbításával az eredeti sorrendre vonatkozó további információkkal. Az elnevezésből adódó látszólagos szükségesség ellenére a stabilitás egyáltalán nem szükséges a helyes rendezéshez, és legtöbbször nem is figyelhető meg, mivel ennek biztosításához szinte mindig többletmemória és idő szükséges.
A [vezetéknév, keresztnév, apanév] formátumú rekordok vezetéknév szerinti rendezésekor az Ivanov Sergey és Ivanov Ivan kulcsértékei ugyanazok lesznek, így a stabil rendezés nem cseréli fel Szergejt és Ivant ( Python 3 , timsort rendezés [1] ):
records = [ { 'vezetéknév' : 'Ivanov' , 'utónév' : 'Sergej' , 'patronymic' : 'Mihajlovics' ,}, { 'vezetéknév' : 'Ivanov' , 'utónév' : 'Iván' , ' apanév' : 'Borisovics' ,}, { 'vezetéknév' : 'Abramov' , 'utónév' : 'Jurij' , 'patronymic' : 'Petrovics' ,}, ] rekordok . sort ( kulcs = lambda x : x [ 'vezetéknév' ]) # rendezés "vezetéknév" kulcs szerint a rekordokban lévő r számára : print ( ' %-12s %-12s %-12s ' % ( r [ 'vezetéknév' ] , r [ 'utónév' ], r [ 'apanév' ]))Ennek eredményeként a rekordok csak vezetéknév szerint lesznek rendezve, miközben az azonos vezetéknévvel rendelkező rekordok között megmarad az eredeti sorrend:
Abramov Jurij Petrovics Ivanov Szergej Mihajlovics Ivanov Ivan BorisovicsA rendezésnek, amely a Burroughs-Wheeler transzformáció fő költségeleme , robusztusnak kell lennie.
Az alábbiakban olyan robusztus rendezési algoritmusok leírása található, amelyek futási ideje nem rosszabb, mint O( n log 2 n ) (kivéve a stabil particionálást használó algoritmus legrosszabb eseteit). Minden pszeudokódban a // perjel pár megjegyzést jelent a sor végére, mint a C++-ban.
Ezzel a rendezési algoritmussal a kezdeti tömb először rekurzívan fel van osztva részekre, amíg a tömb minden része egy vagy nulla elemet nem tartalmaz (a felezést minden rekurziós lépésnél végrehajtják). Ezt követően a kapott részek páronként "összeolvadnak". Az algoritmus általános összetettsége O( n log n ), és az algoritmus további O( n ) memóriát igényel az egyesített tömbök tárolásához.
Ez az algoritmus hasonló a gyorsrendezési algoritmushoz . Csakúgy, mint a gyorsrendezési algoritmusban, ebben az algoritmusban is a kezdeti tömb két részre oszlik - az egyikben minden elem kisebb vagy egyenlő, mint valamelyik pivot elem, a másikban pedig nagyobb vagy egyenlő. Ezt követően a tömb elválasztott részeit ugyanígy rekurzív módon rendezzük. Az algoritmus és a gyorsrendezés közötti különbség az, hogy instabil partíció helyett stabil partíciót használ. Az alábbiakban bemutatjuk ennek az algoritmusnak a megvalósítását pszeudokódban:
Rendezés (a[1..n]) if(n > 1) akkor N ← a[ 1 ]; m ← StablePartition(a[1..n], N); Rendezés(a[1..m]); Rendezés(a[m+1..n]); Stabil partíció (a[1..n], N) ha( n > 1 ) akkor m ← ⌊ n/2 ⌋; m1 ← StablePartition(a[1..m], N); m2 ← m+StablePartition(a[m+1..n], N); Forgatás(a[m1..m2], m); return(m1 + (m2-m)); más if(a[1] < N) akkor return(1); más vissza (0)Forgatási eljárás:
Forgatás (a[1..n], m) if( n > m > 1 ) //a tömbnek legalább két eleme van, és az eltolásnak van értelme műszak ← mn; //eltolandó pozíciók száma gcd ← GCD(m-1, n); //A GCD a legnagyobb közös osztó i ← 0-tól gcd-1-ig csináld fej ← i+1; fejVal ← a[fej]; áram ← fej; következő ← fej+váltás; while(next ≠ head) do a[aktuális] ← a[következő]; jelenlegi ← következő; next ← next+shift; if(next>n) next ← next-n; a[current] ← headVal;O( n log n ) elemi műveletekre van szükség a tömb fenntartható particionálásához . Mivel a végrehajtott rekurzív süllyedés "mélysége" átlagosan O(log n ), az algoritmus összetettsége O( n log² n ). Ebben az esetben az algoritmusnak O(log n ) veremmemóriára lesz szüksége a rekurzió végrehajtásához, bár a legrosszabb esetben a teljes komplexitás O( n ² log n ) és O( n ) memória szükséges .
Az alábbiakban ismertetett összes algoritmus a már rendezett tömbök összevonásán alapul, anélkül, hogy az O(log² n ) veremmemórián kívül további memóriát használna (ez az úgynevezett minimális memóriafeltétel [2] ), és csak az összevonási algoritmusban különböznek. A következő az algoritmusok pszeudokódja (az összevonási algoritmusokat - a Merge eljárást - mindegyik metódushoz külön adjuk meg):
Rendezés (a[1..n]) ha( n > 1 ) akkor m ← n/2 ; Rendezés(a[1..m]); Rendezés(a[m+1..n]); Merge(a[1..n], m); Pratt algoritmusaA Pratt-algoritmusban két elem α és β található rendezett tömbökben , amelyek a mindkét tömb elemeiből álló tömb mediánjai. Ekkor az egész tömb aαbxβy -ként ábrázolható . Ezt követően az elemek ciklikus eltolását hajtjuk végre, aminek eredményeként a következő sorozatot kapjuk: axβαby . Továbbá az egyesítési algoritmus rekurzívan megismétlődik az ax és by tömbök esetében.
Egyesítés(a[1..n], m) if(m ≠ 1 és m ≠ n) //ez a feltétel azt jelenti, hogy a tömbnek legalább 2 elemből kell állnia if( n-1 > 2 ) //azt az esetet, amikor pontosan két elem van, külön kell figyelembe venni if( m-1 > nm ) leftBound←1; rightBound←m; while( leftBound < rightBound ) //keresse a mediánokat ebben a ciklusban m1 ← (leftBound+rightBound)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); //A FindFirstPosition eljárás megvalósítása lásd a következőt. bekezdés if( m1 + (m2-m) > n/2 ) akkor rightBound ← m1-1; más leftBound ← m1+1; Forgatás(a[m1..m2], m); Egyesítés(a[1..m1+(m2-m)], m1); Egyesítés(a[m1+(m2-m)+1..n], m2); más if(a[m] < a[1]) a[m]⟷a[1];Az elemek eltolásához O ( n ) elemműveletekre és O(1) további memóriára van szükség, míg a mediánok megtalálásához két már rendezett tömbben O(log² n ) elemműveletekre és O(1) további memóriára van szükség. Mivel vannak O(log n ) rekurziós lépések, egy ilyen összevonási algoritmus bonyolultsága O( n log n ), a rendezési algoritmus összetettsége pedig O( n log² n ). Ebben az esetben az algoritmusnak O(log² n ) veremmemóriára lesz szüksége.
Algoritmus mediánok keresése nélkülAz előző algoritmusban a mediánok keresésétől a következőképpen szabadulhat meg. A két tömb közül a nagyobbikban válassza ki a középső α elemet (a pivot elemet). Ezután a kisebb tömbben keresse meg egy α-nál nagyobb vagy azzal egyenlő elem első előfordulásának helyét. Nevezzük β-nak. Ezt követően az elemek ciklikusan eltolódnak, mint a Pratt-algoritmusban ( aαbxβy → axβαby ), és a kapott részeket rekurzívan egyesítik. Az összevonási algoritmus pszeudokódja alább látható.
Egyesítés(a[1..n], m) if(m ≠ 1 és m ≠ n) //ez a feltétel azt jelenti, hogy a tömbnek legalább 2 elemből kell állnia if( n-1 > 2 ) //az az eset, amikor pontosan két elemet kell külön-külön figyelembe venni if( m-1 > nm ) m1 ← (m+1)/2 ; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); más m2 ← (n+m)/2 ; m1 ← Find LastPosition(a[1..m], a[ m2 ]); Forgatás(a[m1..m2], m); Egyesítés(a[1..m1+(m2-m)], m1); Egyesítés(a[m1+(m2-m)+1..n], m2); más if(a[ m ] < a[ 1 ]) a[ m ]⟷a[ 1 ];A FindFirstPosition és FindLastPosition eljárások szinte azonosak a bináris keresési eljárással:
FindFirstPosition(a[1..n], x) leftBound ← 1; rightBound ← n; áram ← 1; while(leftBound <rightBound) do aktuális ← ⌊(baloldali határ+jobb határ)/2⌋; if(a[ aktuális ] < x) akkor balra határos ← áram+1 más rightBound ← áram; visszatérés(aktuális); Utolsó pozíció keresése(a[1..n], x) leftBound ← 1; rightBound ← n; áram ← 1; while(leftBound <rightBound) do aktuális ← ⌊(baloldali határ+jobb határ)/2⌋; if( x < a[ jelenlegi ] ) akkor rightBound ← áram; más balra határos ← áram+1 visszatérés(aktuális);A Pratt algoritmussal ellentétben ebben az algoritmusban a particionálás lényegében egyenlőtlen lehet. De még a legrosszabb esetben is az algoritmus a teljes tartományt [ a .. y ] felosztja 3:1 arányban (ha a második tartomány minden eleme nagyobb vagy kisebb, mint a referencia, és mindkét tartomány azonos számú elemek). Ez garantálja a rekurziós lépések logaritmikus számát bármely tömb összevonásakor. Így azt kapjuk, hogy a Pratt-algoritmushoz hasonlóan az egyesítési algoritmus bonyolultsága O( n log n ), a rendezési algoritmus összetettsége O( n log² n ), a szükséges memória pedig O(log² n ). ).
Stabil rendezés extra memória nélkül O( n log n ) időben| Rendezési algoritmusok | |
|---|---|
| Elmélet | Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső |
| Csere | |
| Választás | |
| Betétek | |
| egyesülés | |
| Nincs összehasonlítás | |
| hibrid | |
| Egyéb | |
| nem praktikus | |