Stabil (stabil) sortering - sortering , som inte ändrar den relativa ordningen för sorterade element som har samma nycklar, genom vilka sortering sker.
Stabilitet är en mycket viktig egenskap hos en sorteringsalgoritm, men den kan ändå nästan alltid uppnås genom att förlänga originalnycklarna med ytterligare information om deras ursprungliga ordning. Trots den uppenbara nödvändigheten som antyds av namnet, är stabilitet inte alls nödvändigt för korrekt sortering och observeras oftast inte, eftersom ytterligare minne och tid nästan alltid krävs för att säkerställa det.
När du sorterar poster av formuläret [efternamn, förnamn, patronym] efter efternamn, kommer nyckelvärdena för Ivanov Sergey och Ivanov Ivan att vara desamma, så stabil sortering kommer inte att byta Sergey och Ivan ( Python 3 , timsort sort [1] ):
records = [ { 'surname' : 'Ivanov' , 'first name' : 'Sergey' , 'patronymic' : 'Mikhailovich' ,}, { 'surname' : 'Ivanov' , 'first name' : 'Ivan' , ' patronymic' : 'Borisovich' ,}, { 'surname' : 'Abramov' , 'first name' : 'Yuri' , 'patronymic' : 'Petrovich' ,}, ] poster . sortera ( nyckel = lambda x : x [ 'efternamn' ]) # sortera efter nyckel "efternamn" för r i poster : print ( ' %-12s %-12s %-12s ' % ( r [ 'efternamn' ] , r [ 'förnamn' ], r [ 'patronymic' ]))Som ett resultat kommer poster att sorteras endast efter efternamn, samtidigt som den ursprungliga ordningen behålls bland poster med samma efternamn:
Abramov Yury Petrovich Ivanov Sergey Mikhailovich Ivanov Ivan BorisovichSorteringen, som är den huvudsakliga kostnadsdelen av Burroughs-Wheeler-transformen , måste vara robust.
Nedan finns beskrivningar av robusta sorteringsalgoritmer med körtid som inte är sämre än O( n log 2 n ) (förutom de värsta fallen i algoritmen som använder stabil partitionering). I all pseudokod betyder ett par snedstreck // en kommentar till slutet av raden, som i C++.
Med denna sorteringsalgoritm delas den initiala arrayen först rekursivt i delar tills varje del av arrayen innehåller ett eller noll element (halvering utförs vid varje rekursionssteg). Därefter "slår de resulterande delarna samman i par". Algoritmens övergripande komplexitet är O( n log n ), och algoritmen kräver O( n ) ytterligare minne för att lagra de sammanslagna arrayerna.
Denna algoritm liknar quicksort- algoritmen . Precis som i quicksort-algoritmen, i denna algoritm är den initiala arrayen uppdelad i två delar - i den ena är alla element mindre än eller lika med något pivotelement, och i den andra är de större än eller lika. Därefter sorteras de separerade delarna av arrayen rekursivt på samma sätt. Skillnaden mellan denna algoritm och quicksort-algoritmen är att den använder en stabil partition istället för en instabil. Nedan är implementeringen av denna algoritm i pseudokod:
Sortera(a[1..n]) om(n > 1) då N ← a[1]; m ← StablePartition(a[1..n], N); Sort(a[1..m]); Sortera(a[m+1..n]); StablePartition(a[1..n], N) om(n > 1) då m ← ⌊ n/2 ⌋; m1 ← StablePartition(a[1..m], N); m2 ← m+StabilPartition(a[m+1..n], N); Rotera(a[m1..m2], m); return(m1 + (m2-m)); annan om(a[1] < N) då return(1); annan return(0)Rotera procedur:
Rotera(a[1..n], m) if( n > m > 1 ) //matrisen har minst två element och skiftet är vettigt skift ← mn; //antal positioner som ska flyttas gcd ← GCD(m-1, n); //GCD är den största gemensamma delaren för i ← 0 till gcd-1 gör huvud ← i+1; headVal ← a[huvud]; nuvarande ← huvud; nästa ← huvud+skift; medan(nästa ≠ huvud) gör a[aktuell] ← a[nästa]; nuvarande ← nästa; nästa ← nästa+skift; om(nästa>n) nästa ← nästa-n; a[current] ← headVal;Det krävs O( n log n ) elementära operationer för att partitionera arrayen hållbart . Eftersom "djupet" för den utförda rekursiva nedstigningen är O(log n ) i genomsnitt, är den totala komplexiteten för algoritmen O( n log² n ). I det här fallet kommer algoritmen att kräva O(log n ) stackminne för att utföra rekursion, även om den totala komplexiteten i värsta fall är O( n ² log n ) och O( n ) minne krävs .
Alla algoritmer som beskrivs nedan är baserade på att slå samman redan sorterade arrayer utan att använda ytterligare minne utöver O(log² n ) stackminne (detta är det så kallade minimala minnesvillkoret [2] ) och skiljer sig endast i sammanslagningsalgoritmen. Följande är pseudokoden för algoritmerna (sammanslagningsalgoritmer - Sammanfogningsproceduren - ges separat för varje metod):
Sortera(a[1..n]) om(n > 1) då m ← n/2; Sort(a[1..m]); Sortera(a[m+1..n]); Merge(a[1..n], m); Pratts algoritmI Pratt-algoritmen finns två element α och β i sorterade arrayer , som är medianerna för en array som består av element i båda arrayerna. Då kan hela arrayen representeras som aαbxβy . Därefter utförs en cyklisk förskjutning av element, som ett resultat av vilket vi får följande sekvens: axβαby . Vidare kommer sammanslagningsalgoritmen att upprepas rekursivt för arrayer ax och by.
Merge(a[1..n], m) if(m ≠ 1 och m ≠ n) //detta villkor betyder att arrayen måste ha minst 2 element if( n-1 > 2 ) //fallet när det finns exakt två element måste beaktas separat if( m-1 > nm ) leftBound←1; rightBound←m; while( leftBound < rightBound ) gör //leta efter medianer i denna loop m1 ← (vänstergräns+högergräns)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); //implementering av proceduren FindFirstPosition se nästa. paragraf om( m1 + (m2-m) > n/2) då högerbunden ← m1-1; annan leftBound ← m1+1; Rotera(a[m1..m2], m); Merge(a[1..ml+(m2-m)], ml); Merge(a[ml+(m2-m)+1..n], m2); annan if(a[m] < a[1]) a[m]⟷a[1];Att flytta runt element kräver O( n ) elementoperationer och O(1) ytterligare minne, medan att hitta medianer i två redan sorterade arrayer kräver O(log² n ) elementoperationer och O(1) extra minne. Eftersom det finns O(log n ) rekursionssteg är komplexiteten för en sådan sammanslagningsalgoritm O( n log n ), och den totala komplexiteten för sorteringsalgoritmen är O( n log² n ). I det här fallet kommer algoritmen att kräva O(log² n ) stackminne.
Algoritm utan att söka efter medianerDu kan bli av med sökningen efter medianer i den tidigare algoritmen enligt följande. I den större av de två arrayerna väljer du mittelementet α (pivotelementet). Därefter, i den mindre arrayen, hitta positionen för den första förekomsten av ett element som är större än eller lika med α. Låt oss kalla det β. Därefter skiftas elementen cykliskt, som i Pratt-algoritmen ( aαbxβy → axβαby ), och de erhållna delarna slås rekursivt samman. Pseudokoden för sammanslagningsalgoritmen ges nedan.
Merge(a[1..n], m) if(m ≠ 1 och m ≠ n) //detta villkor betyder att arrayen måste ha minst 2 element if( n-1 > 2 ) //fallet när exakt två element måste betraktas separat if( m-1 > nm ) ml ← (m+1)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); annan m2 ← (n+m)/2; m1 ← FindLastPosition(a[1..m], a[ m2 ]); Rotera(a[m1..m2], m); Merge(a[1..ml+(m2-m)], ml); Merge(a[ml+(m2-m)+1..n], m2); annan if(a[ m ] < a[ 1 ]) a[m]⟷a[1];Procedurerna FindFirstPosition och FindLastPosition är nästan identiska med den binära sökproceduren:
FindFirstPosition(a[1..n], x) leftBound ← 1; högergräns ← n; aktuell ← 1; while(leftBound <rightBound) gör aktuell ← ⌊(vänstergräns+högergräns)/2⌋; if(a[ aktuell ] < x) alltså leftBound ← aktuell+1 annan rightBound ← ström; return(aktuell); FindLastPosition(a[1..n], x) leftBound ← 1; högergräns ← n; aktuell ← 1; while(leftBound <rightBound) gör aktuell ← ⌊(vänstergräns+högergräns)/2⌋; if( x < a[ aktuell ] ) då rightBound ← ström; annan leftBound ← aktuell+1 return(aktuell);I motsats till Pratt-algoritmen kan partitioneringen i denna algoritm vara väsentligt ojämlik. Men även i värsta fall kommer algoritmen att dela upp hela området [ a .. y ] i förhållandet 3:1 (om alla element i det andra området är större eller mindre än referensen och båda områdena har lika många av element). Detta garanterar ett logaritmiskt antal rekursionssteg vid sammanslagning av alla arrayer. Således får vi att, precis som i Pratt-algoritmen, är komplexiteten för sammanslagningsalgoritmen O( n log n ), komplexiteten för sorteringsalgoritmen är O( n log² n ), och det nödvändiga minnet är O(log² n ). ).
Stabil sortering utan extra minne i O( n log n ) tid| Sorteringsalgoritmer | |
|---|---|
| Teori | Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern |
| Utbyta | |
| Val | |
| Insatser | |
| fusion | |
| Inga jämförelser | |
| hybrid | |
| Övrig | |
| opraktisk | |