Stabil (stabil) sortering - sortering , som ikke ændrer den relative rækkefølge af sorterede elementer, der har de samme nøgler, som sorteringen sker ved.
Stabilitet er en meget vigtig egenskab ved en sorteringsalgoritme, men ikke desto mindre kan den næsten altid opnås ved at forlænge de originale nøgler med yderligere information om deres oprindelige rækkefølge. På trods af den tilsyneladende nødvendighed, som navnet antyder, er stabilitet slet ikke nødvendig for korrekt sortering og observeres oftest ikke, da der næsten altid kræves ekstra hukommelse og tid for at sikre det.
Ved sortering af registreringer af formen [efternavn, fornavn, patronym] efter efternavn, vil nøgleværdierne for Ivanov Sergey og Ivanov Ivan være de samme, så stabil sortering vil ikke bytte Sergey og 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' ,}, ] optegnelser . sort ( nøgle = lambda x : x [ 'efternavn' ]) # sorter efter nøgle "efternavn" for r i poster : print ( ' %-12s %-12s %-12s ' % ( r [ 'efternavn' ] , r [ 'fornavn' ], r [ 'patronymic' ]))Som et resultat vil poster kun blive sorteret efter efternavn, mens den oprindelige rækkefølge mellem poster med samme efternavn bevares:
Abramov Yury Petrovich Ivanov Sergey Mikhailovich Ivanov Ivan BorisovichSortering, som er hovedomkostningselementet i Burroughs-Wheeler-transformationen , skal være robust.
Nedenfor er beskrivelser af robuste sorteringsalgoritmer med køretid, der ikke er dårligere end O( n log 2 n ) (bortset fra de værste tilfælde i algoritmen ved brug af stabil partitionering). I al pseudokode betyder et par skråstreger // en kommentar til slutningen af linjen, som i C++.
Med denne sorteringsalgoritme opdeles det indledende array først rekursivt i dele, indtil hver del af arrayet indeholder et eller nul elementer (halvering udføres ved hvert rekursionstrin). Derefter "smelter de resulterende dele i par". Algoritmens overordnede kompleksitet er O( n log n ), og algoritmen kræver O( n ) yderligere hukommelse for at gemme de flettede arrays.
Denne algoritme ligner quicksort- algoritmen . Ligesom i quicksort-algoritmen, i denne algoritme er det indledende array opdelt i to dele - i den ene er alle elementer mindre end eller lig med et pivotelement, og i den anden er de større end eller lig. Derefter sorteres de adskilte dele af arrayet rekursivt på samme måde. Forskellen mellem denne algoritme og quicksort-algoritmen er, at den bruger en stabil partition i stedet for en ustabil. Nedenfor er implementeringen af denne algoritme i pseudokode:
Sort(a[1..n]) hvis(n > 1) så N ← a[ 1 ]; m ← StablePartition(a[1..n], N); Sort(a[1..m]); Sort(a[m+1..n]); StablePartition(a[1..n], N) hvis(n > 1) så m ← ⌊ n/2 ⌋; m1 ← StablePartition(a[1..m], N); m2 ← m+StabilPartition(a[m+1..n], N); Roter(a[m1..m2], m); return(m1 + (m2-m)); andet hvis(a[1] < N) så return(1); andet returnere (0)Rotationsprocedure:
Roter(a[1..n], m) if( n > m > 1 ) //arrayet har mindst to elementer, og skiftet giver mening skift ← mn; //antal stillinger, der skal flyttes gcd ← GCD(m-1, n); //GCD er den største fælles divisor for i ← 0 til gcd-1 do hoved ← i+1; headVal ← a[hoved]; nuværende ← hoved; næste ← hoved+skift; mens (næste ≠ hoved) gør a[aktuel] ← en[næste]; nuværende ← næste; næste ← næste+skift; hvis(næste>n) næste ← næste-n; a[current] ← headVal;Det kræver O( n log n ) elementære operationer at opdele arrayet bæredygtigt . Da "dybden" af den udførte rekursive nedstigning er O(log n ) i gennemsnit, er den overordnede kompleksitet af algoritmen O( n log² n ). I dette tilfælde vil algoritmen kræve O(log n ) stakhukommelse for at udføre rekursion, selvom den samlede kompleksitet i værste tilfælde er O( n ² log n ) og O( n ) hukommelse er påkrævet .
Alle de algoritmer, der er beskrevet nedenfor, er baseret på at flette allerede sorterede arrays uden at bruge yderligere hukommelse ud over O(log² n ) stack-hukommelse (dette er den såkaldte minimum memory condition [2] ) og adskiller sig kun i flettealgoritmen. Følgende er pseudokoden for algoritmerne (fletningsalgoritmer - fletteproceduren - gives separat for hver metode):
Sort(a[1..n]) hvis(n > 1) så m ← n/2 ; Sort(a[1..m]); Sort(a[m+1..n]); Merge(a[1..n], m); Pratts algoritmeI Pratt-algoritmen findes to elementer α og β i sorterede arrays , som er medianerne af et array bestående af elementer fra begge arrays. Så kan hele arrayet repræsenteres som aαbxβy . Derefter udføres et cyklisk skift af elementer, som et resultat af hvilket vi opnår følgende sekvens: axβαby . Yderligere vil flettealgoritmen blive gentaget rekursivt for arrays ax og by.
Flet(a[1..n], m) if(m ≠ 1 og m ≠ n) //denne betingelse betyder, at arrayet skal have mindst 2 elementer if( n-1 > 2 ) //tilfældet, hvor der er præcis to elementer, skal betragtes separat if( m-1 > nm ) leftBound←1; rightBound←m; while( leftBound < rightBound ) gør //se efter medianer i denne løkke m1 ← (venstregrænse+højregrænse)/2; m2 ← FindFirstPosition(a[m..n], a[m1]); //implementering af procedure FindFirstPosition se næste. afsnit if( m1 + (m2-m) > n/2 ) derefter højrebundet ← m1-1; andet venstrebundet ← m1+1; Roter(a[m1..m2], m); Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2); andet if(a[m] < a[1]) a[m]⟷a[1];At flytte elementer rundt kræver O( n ) elementoperationer og O(1) ekstra hukommelse, mens at finde medianer i to allerede sorterede arrays kræver O(log² n ) element operationer og O(1) yderligere hukommelse. Da der er O(log n ) rekursionstrin, er kompleksiteten af en sådan flettealgoritme O( n log n ), og den overordnede kompleksitet af sorteringsalgoritmen er O( n log² n ). I dette tilfælde vil algoritmen kræve O(log² n ) stakhukommelse.
Algoritme uden at søge efter medianerDu kan slippe af med søgningen efter medianer i den tidligere algoritme som følger. I det største af de to arrays skal du vælge det midterste element α (pivotelementet). Find derefter positionen for den første forekomst af et element, der er større end eller lig med α, i den mindre matrix. Lad os kalde det β. Derefter forskydes elementerne cyklisk, som i Pratt-algoritmen ( aαbxβy → axβαby ), og de opnåede dele flettes rekursivt sammen. Pseudokoden for flettealgoritmen er angivet nedenfor.
Flet(a[1..n], m) if(m ≠ 1 og m ≠ n) //denne betingelse betyder, at arrayet skal have mindst 2 elementer if( n-1 > 2 ) //tilfældet, hvor præcis to elementer skal betragtes separat if( m-1 > nm ) ml ← (m+1)/2; m2 ← FindFirstPosition(a[m..n], a[m1]); andet m2 ← (n+m)/2; m1 ← FindLastPosition(a[1..m], a[ m2 ]); Roter(a[m1..m2], m); Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2); andet if(a[ m ] < a[ 1 ]) a[m]⟷a[1];FindFirstPosition- og FindLastPosition-procedurerne er næsten identiske med den binære søgeprocedure:
FindFirstPosition(a[1..n], x) leftBound ← 1; højrebundet ← n; nuværende ← 1; while(venstregrænse < højregrænse) gør nuværende ← ⌊(venstregrænse+højregrænse)/2⌋; if(a[ aktuel ] < x) så leftBound ← nuværende+1 andet højreBound ← nuværende; return(aktuel); FindLastPosition(a[1..n], x) leftBound ← 1; højrebundet ← n; nuværende ← 1; while(venstregrænse < højregrænse) gør nuværende ← ⌊(venstregrænse+højregrænse)/2⌋; if( x < a[ aktuel ] ) så højreBound ← nuværende; andet leftBound ← nuværende+1 return(aktuel);I modsætning til Pratt-algoritmen kan partitioneringen i denne algoritme være væsentligt ulige. Men selv i værste tilfælde vil algoritmen opdele hele området [ a .. y ] i forholdet 3:1 (hvis alle elementer i det andet område er større eller mindre end referencen, og begge områder har lige mange af elementer). Dette garanterer et logaritmisk antal rekursionstrin ved sammenlægning af arrays. Således får vi, ligesom i Pratt-algoritmen, kompleksiteten af flettealgoritmen er O( n log n ), kompleksiteten af sorteringsalgoritmen er O( n log² n ), og den nødvendige hukommelse er O(log² n ). ).
Stabil sortering uden ekstra hukommelse i O( n log n ) tid| Sorteringsalgoritmer | |
|---|---|
| Teori | Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern |
| Udveksling | |
| Valg | |
| indsætter | |
| fusion | |
| Ingen sammenligninger | |
| hybrid | |
| Andet | |
| upraktisk | |