Stabilirea stabilă este un tip care nu modifică ordinea relativă a elementelor sortate care au aceleași taste.
Stabilitatea este o caracteristică foarte importantă a algoritmului de sortare, dar, totuși, poate fi aproape întotdeauna realizată prin extinderea cheilor sursă în detrimentul informațiilor suplimentare despre ordinea inițială. În ciuda nevoii aparentă care decurge din denumire, durabilitatea nu este deloc necesară pentru sortarea corectă și, cel mai adesea, nu este respectată, deoarece este aproape întotdeauna necesară o memorie și un timp suplimentar pentru furnizarea acesteia.
Atunci când sortarea înregistrările de forma [numele, prenumele] privind valorile-cheie pentru numele Serghei Ivanov și Ivan Ivanov va fi la fel, astfel încât un stabil sortare neîncetat lui Serghei și Ivan locuri (Python 3. sortare timsort [1]):
Prin urmare, intrările vor fi sortate numai după numele de familie, păstrând ordinea inițială printre înregistrările cu aceleași nume de familie:
Sortare, care este elementul principal de cost al transformării Burrows-Wheeler. ar trebui să fie durabilă.
Algoritmi de sortare stabilă
Îmbinarea cu memorie suplimentară
Cu acest algoritm, sortarea se efectuează prima divizie recursivă în părți ale șirului original, atât timp cât fiecare dintre matrice nu unul sau zero elemente (pe fiecare pas recursie separarea se efectuează în jumătate). După aceasta, piesele rezultate sunt "îmbinate" în perechi. Complexitatea totală a algoritmului - O (n log n), în care algoritmul ia O (n) mai multe matrice de memorie pentru stocarea de fuziune.
Sortare utilizând o separare stabilă
Acest algoritm este similar algoritmului de sortare rapidă. La fel ca și un algoritm de sortare rapidă, matrice sursă algoritm este împărțită în două tranșe - una în toate elementele este mai mică sau egală cu unele element suport, iar celălalt - mai mare sau egal. După aceea, părțile divizate ale matricei sunt sortate recursiv în același mod. Diferența dintre acest algoritm și algoritmul de sortare rapidă constă în faptul că acesta utilizează o separare stabilă în loc de una instabilă. Mai jos este implementarea acestui algoritm pe un pseudocod:
Pentru partiționarea stabilă a matricei sunt necesare operații elementare O (n log n). Deoarece "adâncimea" coborârii recursive efectuată în cazul mediu este O (log n), complexitatea generală a algoritmului este O (n log² n). Algoritmul de implementare a recursiunii va necesita O (log n) memoriei stack-ului, deși în cel mai rău caz, complexitatea totală este O (n ² log n) și memoria O (n) este necesară.
Algoritmi pentru sortarea unei îmbinări fără memorie suplimentară
Toate următorii algoritmi se bazează pe fuziunea este deja sortat matrice, fără utilizarea de memorie suplimentară dincolo de O (log² n) stivă (care - .. așa-numita condiție de memorie minimă [2]) și diferă numai în algoritmul de fuziune. Următorul cod este un pseudocod al algoritmilor (algoritmii de îmbinare - Procedura de fuziune - sunt date separat pentru fiecare metodă):
Algoritmul Pratt
În algoritmul Pratt, în matricele sortate, se găsesc două elemente α și β. care sunt medii ale unei matrice compuse din elemente ale ambelor tablouri. Apoi întreaga matrice poate fi reprezentată ca aαbxβy. După aceasta elementele sunt deplasate ciclic, rezultând următoarea secvență: axabi. Apoi, algoritmul de îmbinare este repetat repetat pentru topor și matrice.
Elementul de schimbare ciclică necesită O (n) operațiilor elementare și O (1) memorie suplimentară și căutarea în două medianele sortate deja matrice - O (log² n) operațiilor elementare și O (1) memorie suplimentară. Deoarece O efectuat (log n) pași recursie, complexitatea unui astfel de algoritm este O contopire (log n), și complexitatea generală a algoritmului de sortare - O (n log² n). Algoritmul necesită O (log² n) din memoria stack-ului.
Algoritm fără căutare mediană
Din căutarea medianilor din algoritmul anterior, puteți să scăpați de următorul mod. În cel mai mare dintre cele două matrice, selectăm elementul intermediar α (elementul de susținere). Apoi, într-o matrice mai mică, găsim poziția primei apariții a unui element mai mare sau egal cu α. O numim β. După aceasta, elementele sunt deplasate în același mod ca și în algoritmul lui Pratt (aαbxβy → axbaby) și se efectuează fuziunea recursivă a pieselor obținute. Codul pseudo al algoritmului de îmbinare este prezentat mai jos.
Procedurile FindFirstPosition și FindLastPosition aproape coincid cu procedura de căutare binară:
Spre deosebire de algoritmul Pratt, în acest algoritm partiționarea poate fi în esență inegal. Dar chiar și în cel mai rău caz, algoritmul va rupe întregul interval [a. y] în raportul 3: 1 (în cazul în care toate elementele de-a doua bandă va fi mai mare sau mai mică decât de referință și astfel ambele benzi au același număr de elemente). Acest lucru asigură un număr logaritmic de etape de recursiune atunci când fuzionează orice matrice. Astfel vedem că în același mod ca și în algoritmul Pratt, complexitatea fuziunii algoritmului este O (n log n), complexitatea unui algoritm de sortare - O (n log² n), iar memoria necesară - O (log² n).
Sortarea stabilă fără memorie suplimentară în timp O (n log n)
Modalități de îmbunătățire a algoritmilor
- În toate algoritmii de mai sus, atunci când partiționează matricea sursă în părți, partiționarea recursivă poate fi oprită dacă dimensiunea matricei care trebuie fragmentată devine suficient de mică. Apoi, puteți aplica oricare dintre algoritmii de sortare simplificați (de exemplu, introduceți sortarea), despre care se știe că funcționează mai rapid decât cele complexe, dacă dimensiunea matricei de intrare este mică. De fapt, această tehnică este aplicabilă nu numai algoritmilor prezentați aici, ci și oricărui alt algoritm în care este aplicată partiționarea recursivă a matricei originale (de exemplu, sortarea rapidă instabilă rapidă). Numărul specific al elementelor de intrare la care se trece la un algoritm simplu de sortare depinde de computerul utilizat.
- În algoritmul lui Pratt, un algoritm fără cautarea medianilor și a unui algoritm care utilizează o separare stabilă, în loc de apelarea recursivă a unei proceduri de îmbinare de fiecare dată, puteți aloca dinamic o serie de variabile temporare. Apoi, va fi posibilă continuarea divizării intervalului numai până când numărul de elemente din intervalul mai mare devine mai mic sau egal cu capacitatea matricei temporare. De fapt, la un anumit pas al recurgerii, algoritmul lui Pratt și algoritmul fără a căuta mediani se transformă într-un algoritm de simplă fuziune. Astfel. dacă sistemul are suficientă memorie dinamică, atunci timpul de operare asimptotic poate fi adus la O (n log n) în loc de O (n log² n).
Articole similare
Trimiteți-le prietenilor: