Sortare stabilă (stabilă) - sortare , care nu modifică ordinea relativă a elementelor sortate care au aceleași chei, prin care are loc sortarea.
Stabilitatea este o caracteristică foarte importantă a unui algoritm de sortare, dar cu toate acestea aproape întotdeauna poate fi obținută prin prelungirea cheilor originale cu informații suplimentare despre ordinea lor inițială. În ciuda aparentei necesități pe care o implică numele, stabilitatea nu este deloc necesară pentru sortarea corectă și de cele mai multe ori nu este respectată, deoarece aproape întotdeauna sunt necesare memorie și timp suplimentar pentru a o asigura.
Atunci când sortați înregistrările cu forma [nume, prenume, patronimic] după nume de familie, valorile cheie pentru Ivanov Sergey și Ivanov Ivan vor fi aceleași, astfel încât sortarea stabilă nu va schimba Serghei și Ivan ( Python 3 , sortare timsort [1] ):
records = [ { 'prenume' : 'Ivanov' , 'prenume' : 'Serghey' , 'patronimic' : 'Mikhailovici' ,}, { 'prenume' : 'Ivanov' , 'prenume' : 'Ivan' , ' patronymic' : 'Borisovich' ,}, { 'nume' : 'Abramov' , 'prenume' : 'Yuri' , 'patronimic' : 'Petrovici' ,}, ] înregistrări . sort ( cheie = lambda x : x [ 'nume de familie' ]) # sortează după cheie "nume de familie" pentru r în înregistrări : print ( ' %-12s %-12s %-12s ' % ( r [ 'nume' ] , r [ „prenume” ], r [ „patronimic” ]))Ca urmare, înregistrările vor fi sortate numai după nume de familie, păstrând ordinea inițială între înregistrările cu același nume de familie:
Abramov Iuri Petrovici Ivanov Serghei Mihailovici Ivanov Ivan BorisoviciSortarea, care este principalul element de cost al transformării Burroughs-Wheeler , trebuie să fie robustă.
Mai jos sunt descrieri ale algoritmilor de sortare robusti cu un timp de rulare nu mai rău decât O( n log 2 n ) (cu excepția celor mai rele cazuri din algoritmul care utilizează partiționare stabilă). În tot pseudocodul, o pereche de bare oblice // înseamnă un comentariu la sfârșitul liniei, ca în C++.
Cu acest algoritm de sortare, tabloul inițial este mai întâi împărțit recursiv în părți până când fiecare parte a matricei conține unul sau zero elemente (înjumătățirea este efectuată la fiecare pas de recursivitate). După aceea, părțile rezultate în perechi „unesc”. Complexitatea generală a algoritmului este O( n log n ), iar algoritmul necesită O( n ) memorie suplimentară pentru a stoca tablourile îmbinate.
Acest algoritm este similar cu algoritmul de sortare rapidă . La fel ca în algoritmul de sortare rapidă, în acest algoritm matricea inițială este împărțită în două părți - într-una, toate elementele sunt mai mici sau egale cu un element pivot, iar în cealaltă, sunt mai mari sau egale. După aceea, părțile separate ale matricei sunt sortate recursiv în același mod. Diferența dintre acest algoritm și algoritmul de sortare rapidă este că folosește o partiție stabilă în loc de una instabilă. Mai jos este implementarea acestui algoritm în pseudocod:
Sortare(a[1..n]) dacă (n > 1) atunci N ← a[ 1 ]; m ← StablePartition(a[1..n], N); Sortare(a[1..m]); Sortare(a[m+1..n]); StablePartition(a[1..n], N) dacă ( n > 1 ) atunci m ← ⌊ n/2 ⌋; m1 ← StablePartition(a[1..m], N); m2 ← m+StablePartition(a[m+1..n], N); Rotire(a[m1..m2], m); întoarcere(m1 + (m2-m)); altfel dacă(a[1] < N) atunci întoarcere(1); altfel întoarcere(0)Procedura de rotire:
Rotiți(a[1..n], m) if( n > m > 1 ) //matricea are cel puțin două elemente și deplasarea are sens shift ← mn; //numărul de posturi de schimbat gcd ← GCD(m-1, n); //GCD este cel mai mare divizor comun pentru i ← 0 la mcd-1 do cap ← i+1; headVal ← a[head]; curent ← cap; următorul ← cap+shift; în timp ce(următorul ≠ cap) face a[curent] ← a[next]; curent ← următorul; următorul ← următorul+shift; dacă(următorul>n) următorul ← următorul-n; a[curent] ← headVal;Este nevoie de operații elementare O( n log n ) pentru a partiționa în mod sustenabil matricea . Deoarece „adâncimea” coborârii recursive efectuate este O(log n ) în medie, complexitatea generală a algoritmului este O( n log² n ). În acest caz, algoritmul va necesita memoria stivă O(log n ) pentru a efectua recursiunea, deși în cel mai rău caz, complexitatea totală este O( n² log n ) și este necesară memoria O( n ).
Toți algoritmii descriși mai jos se bazează pe îmbinarea matricelor deja sortate fără a utiliza memorie suplimentară dincolo de memoria stivei O(log² n ) (aceasta este așa-numita condiție de memorie minimă [2] ) și diferă doar în algoritmul de îmbinare. Următorul este pseudocodul algoritmilor (algoritmii de îmbinare - procedura Merge - sunt dați separat pentru fiecare metodă):
Sortare(a[1..n]) dacă ( n > 1 ) atunci m ← n/2 ; Sortare(a[1..m]); Sortare(a[m+1..n]); Merge(a[1..n], m); Algoritmul lui PrattÎn algoritmul Pratt, două elemente α și β se găsesc în rețele sortate , care sunt medianele unui tablou format din elemente ale ambelor matrice. Apoi întreaga matrice poate fi reprezentată ca aαbxβy . După aceea, se efectuează o deplasare ciclică a elementelor, în urma căreia obținem următoarea succesiune: axβαby . În plus, algoritmul de îmbinare va fi repetat recursiv pentru tablourile ax și by.
Merge(a[1..n], m) if(m ≠ 1 și m ≠ n) //această condiție înseamnă că tabloul trebuie să aibă cel puțin 2 elemente if( n-1 > 2 ) //cazul când există exact două elemente trebuie luat în considerare separat dacă ( m-1 > nm ) leftBound←1; dreaptaBound←m; while( leftBound < rightBound ) nu //căutați medianele în această buclă m1 ← (leftBound+rightBound)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); //implementarea procedurii FindFirstPosition vezi în continuare. paragraf dacă( m1 + (m2-m) > n/2 ) atunci dreaptaBound ← m1-1; altfel leftBound ← m1+1; Rotire(a[m1..m2], m); Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2); altfel dacă(a[m] <a[1]) a[m]⟷a[1];Deplasarea elementelor necesită operații cu elemente O( n ) și memorie suplimentară O(1), în timp ce găsirea medianelor în două tablouri deja sortate necesită operații cu elemente O(log² n ) și memorie suplimentară O(1). Deoarece există pași de recursivitate O(log n ), complexitatea unui astfel de algoritm de îmbinare este O( n log n ), iar complexitatea generală a algoritmului de sortare este O( n log² n ). În acest caz, algoritmul va necesita memorie stivă O(log² n ).
Algoritm fără căutarea medianelorPuteți scăpa de căutarea medianelor din algoritmul anterior, după cum urmează. În cea mai mare dintre cele două matrice, selectați elementul din mijloc α (elementul pivot). Apoi, în matricea mai mică, găsiți poziția primei apariții a unui element mai mare sau egal cu α. Să-i spunem β. După aceea, elementele sunt deplasate ciclic, ca în algoritmul Pratt ( aαbxβy → axβαby ), iar părțile obținute sunt îmbinate recursiv. Pseudocodul algoritmului de îmbinare este prezentat mai jos.
Merge(a[1..n], m) if(m ≠ 1 și m ≠ n) //această condiție înseamnă că tabloul trebuie să aibă cel puțin 2 elemente if( n-1 > 2 ) //cazul când exact două elemente trebuie luate în considerare separat dacă ( m-1 > nm ) m1 ← (m+1)/2; m2 ← FindFirstPosition(a[m..n], a[ m1 ]); altfel m2 ← (n+m)/2; m1 ← FindLastPosition(a[1..m], a[ m2 ]); Rotire(a[m1..m2], m); Merge(a[1..m1+(m2-m)], m1); Merge(a[m1+(m2-m)+1..n], m2); altfel dacă(a[m] <a[1]) a[m]⟷a[1];Procedurile FindFirstPosition și FindLastPosition sunt aproape identice cu procedura de căutare binară:
FindFirstPosition(a[1..n], x) leftBound ← 1; dreaptaBound ← n; curent ← 1; while(leftBound < rightBound) do curent ← ⌊(leftBound+rightBound)/2⌋; dacă(a[ curent ] < x) atunci leftBound ← curent+1 altfel dreaptaBound ← curent; return(curent); GăsițiUltimaPoziție(a[1..n], x) leftBound ← 1; dreaptaBound ← n; curent ← 1; while(leftBound < rightBound) do curent ← ⌊(leftBound+rightBound)/2⌋; dacă( x < a[ curent ] ) atunci dreaptaBound ← curent; altfel leftBound ← curent+1 return(curent);Spre deosebire de algoritmul Pratt, în acest algoritm partiționarea poate fi substanțial inegală. Dar chiar și în cel mai rău caz, algoritmul va împărți întregul interval [ a .. y ] într-un raport de 3:1 (dacă toate elementele celui de-al doilea interval sunt mai mari sau mai mici decât cel de referință și ambele intervale au un număr egal de elemente). Acest lucru garantează un număr logaritmic de pași de recursivitate la îmbinarea oricăror tablouri. Astfel, obținem că, la fel ca în algoritmul Pratt, complexitatea algoritmului de îmbinare este O( n log n ), complexitatea algoritmului de sortare este O( n log² n ), iar memoria necesară este O(log² n ). ).
Sortare stabilă fără memorie suplimentară în timp O( n log n )| Algoritmi de sortare | |
|---|---|
| Teorie | Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern |
| schimb valutar | |
| Alegere | |
| inserții | |
| fuziune | |
| Fara comparatii | |
| hibrid | |
| Alte | |
| nepractic | |