Sortare radix

sortare radix
Autor	Hollerith, Herman
scop	Algoritm de sortare
Structură de date	matrice
cel mai rău moment	, unde w este numărul de biți necesari pentru a stoca fiecare cheie.
Costul memoriei
Fișiere media la Wikimedia Commons

Sortarea pe biți ( eng.  radix sort ) este un algoritm de sortare care rulează în timp liniar. Există opțiuni stabile .

Algoritm

Destinat inițial pentru sortarea numerelor întregi scrise ca cifre. Dar, deoarece în memoria computerelor orice informație este înregistrată ca numere întregi, algoritmul este potrivit pentru sortarea oricăror obiecte, a căror înregistrare poate fi împărțită în „cifre” care conțin valori comparabile. De exemplu, în acest fel puteți sorta nu numai numerele scrise ca un set de numere, ci și șiruri care sunt un set de caractere și, în general, valori arbitrare în memorie, reprezentate ca un set de octeți.

Comparația se realizează bit cu bit: mai întâi, se compară valorile unei cifre extreme, iar elementele sunt grupate în funcție de rezultatele acestei comparații, apoi se compară valorile următoarei cifre, adiacente și elementele sunt fie ordonate după rezultatele comparării valorilor acestei cifre în cadrul grupurilor formate în trecerea anterioară, fie reordonate în ansamblu, păstrând însă ordinea relativă realizată de sortarea anterioară. Apoi se procedează la fel pentru următoarea descărcare și așa mai departe până la final.

Deoarece este posibil să se alinieze înregistrările comparate unele față de altele în direcții diferite, în practică există două opțiuni pentru această sortare. Pentru numere, ele sunt numite în ceea ce privește semnificația cifrelor numărului și se dovedește astfel: puteți alinia intrările de numere către cifre mai puțin semnificative (în partea dreaptă, spre cele, cifră cea mai puțin semnificativă, LSD ) sau cifre mai semnificative (în partea stângă, din cifre mai semnificative, cifra cea mai semnificativă, MSD).

Cu sortarea LSD (sortarea cu alinierea după cifra cea mai puțin semnificativă, la dreapta, la unii), se obține ordinea potrivită pentru numere. De exemplu: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. Adică aici valorile sunt mai întâi sortate după unități, apoi sortate după zeci, păstrând sortarea după unități în interior zeci, apoi cu sute, păstrând sortarea pe zeci și unități în sute etc.

Sortarea MSD (de ordine superioară, aliniată la stânga) are ca rezultat o ordine alfabetică, care este adecvată pentru sortarea liniilor de text. De exemplu, „b, c, d, e, f, g, h, i, j, ba” va sorta ca „b, ba, c, d, e, f, g, h, i, j”. Dacă MSD este aplicat numerelor date în exemplu, obținem secvența 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Puteți acumula informații despre grupuri la fiecare trecere în moduri diferite - de exemplu, în liste, în arbori, în matrice, notând fie elementele în sine, fie indicii acestora etc.

Există o versiune instabilă a sortării recursive pe biți, care se realizează direct în matricea sortată: la prima trecere, mișcarea se îndreaptă una spre alta, la începutul matricei, este căutat un element cu 1 în prima cifră de biți, la sfârșitul matricei se caută un element cu 0 în aceeași cifră. Elementele găsite sunt schimbate și așa mai departe până când indicii în cauză se întâlnesc. Astfel, la începutul matricei, înainte de punctul de întâlnire al indicilor, sunt colectate toate elementele cu un bit egal cu 0, iar după acest index, toate elementele cu un bit egal cu 1. Apoi, recursiv, puteți în mod complet similar. iterează prin sub-intervalele rezultate ale matricei, comparând valorile celui de-al doilea și al următorilor biți și rearanjează locurile elementelor.

Aplicație pentru rânduri în varianta sortare coș

Sortarea coșului poate fi folosită pentru a sorta după rang . Fiecare categorie se desfășoară de două ori. La prima trecere, se numără numărul anumitor valori din această categorie. Apoi, pentru fiecare valoare posibilă, matricele sunt pregătite pentru a stoca elementele cu acea valoare. În timpul celei de-a doua treceri, elementele în sine sunt scrise în aceste matrice. O implementare eficientă este posibilă prin utilizarea unei matrice de referințe de șir în locul șirurilor în sine și a unei matrice suplimentare de „dimensiuni bin” inițializate la prima trecere cu numărul de elemente din fiecare „bin”.

A doua trecere și următoarele se efectuează separat pe fiecare coș obținut în trecerea anterioară, împărțindu-l în „subcoșuri” și comparând caracterele secunde și, respectiv, ulterioare ale șirurilor.

Operația se termină când este atinsă lungimea maximă a șirului sau când toate „subcoșurile” au lungimea de 1.

Note

Literatură

• Donald Knuth . The Art of Computer Programming, Volumul 3. Sorting and Searching = The Art of Computer Programming, vol.3. Sortare și căutare. - Ed. a II-a. - M . : „Williams” , 2007. - S. 192-201. — ISBN 5-8459-0082-4 .

Link -uri

• Visualizer1  este un applet Java.
• Visualizer2  este un applet Java.
• Implementarea algoritmului în C++ Arhivat 27 iulie 2019 la Wayback Machine .