Radix sortera

radix sortera
Författare	Hollerith, Herman
ändamål	Sorteringsalgoritm
Datastruktur	array
värsta tiden	där w är antalet bitar som krävs för att lagra varje nyckel.
Minneskostnad
Mediafiler på Wikimedia Commons

Bitvis sortering ( eng.  radix sort ) är en sorteringsalgoritm som körs i linjär tid. Det finns stabila alternativ.

Algoritm

Ursprungligen avsedd för att sortera heltal skrivna som siffror. Men eftersom all information i datorernas minne registreras som heltal, är algoritmen lämplig för att sortera alla objekt, vars post kan delas in i "siffror" som innehåller jämförbara värden. På det här sättet kan du till exempel sortera inte bara siffror skrivna som en uppsättning siffror, utan också strängar som är en uppsättning tecken, och i allmänhet godtyckliga värden i minnet, representerade som en uppsättning byte.

Jämförelsen utförs bit för bit: först jämförs värdena för en extremsiffra, och elementen grupperas enligt resultaten av denna jämförelse, sedan jämförs värdena för nästa siffra, intill, och elementen är antingen ordnade efter resultaten av att jämföra värdena för denna siffra inom grupperna som bildades i föregående pass, eller omordnade som en helhet, men bevarar den relativa ordningen som uppnåtts av den tidigare sorten. Sedan görs samma sak för nästa urladdning, och så vidare till slutet.

Eftersom det är möjligt att justera de jämförda posterna relativt varandra i olika riktningar, finns det i praktiken två alternativ för denna sortering. För siffror kallas de i termer av betydelsen av siffrorna i numret, och det blir så här: du kan anpassa inmatningarna av siffror mot mindre signifikanta siffror (på höger sida, mot ettor, minst signifikanta siffror, LSD ) eller mer signifikanta siffror (på vänster sida, från mer signifikanta siffror, mest signifikanta siffror, MSD).

Med LSD-sortering (sortering med justering med den minst signifikanta siffran, till höger, till ettor) erhålls den ordning som är lämplig för siffror. Till exempel: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. Det vill säga, här sorteras värdena först efter ettor, sedan sorterade efter tiotal, och håller sorteringen efter ettor inuti tiotal, sedan hundratals, hålla sortering efter tiotal och enheter inom hundratals osv.

MSD-sortering (hög ordning, vänsterjusterad) resulterar i alfabetisk ordning, vilket är lämpligt för att sortera textrader. Till exempel "b, c, d, e, f, g, h, i, j, ba" kommer att sorteras som "b, ba, c, d, e, f, g, h, i, j". Om MSD appliceras på talen som anges i exemplet får vi sekvensen 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Du kan samla information om grupper vid varje pass på olika sätt - till exempel i listor, i träd, i arrayer, skriva ut antingen själva elementen eller deras index, etc.

Det finns en instabil version av rekursiv bitvis sortering, som utförs direkt i den sorterade arrayen: vid första passet går rörelsen mot varandra, i början av arrayen genomsöks ett element med 1 i den första bitsiffran, i slutet av matrisen söks ett element med 0 i samma siffra. De hittade elementen byts ut och så vidare tills de aktuella indexen möts. Alltså, i början av arrayen, före mötespunkten för indexen, samlas alla element med en bit lika med 0, och efter detta index, alla element med en bit lika med 1. Sedan, rekursivt, kan du helt likadant iterera genom de resulterande underområdena i arrayen, jämför värdena för den andra och efterföljande bitarna och ordna om elementens platser.

Applikation för rader i korgsorteringsvarianten

Korgsortering kan användas för att sortera efter rang . Varje kategori körs två gånger. Vid det första passet räknas antalet vissa värden i denna kategori. Sedan förbereds arrayer för varje möjligt värde för att lagra elementen med det värdet. Under det andra passet skrivs själva elementen ut till dessa arrayer. En effektiv implementering är möjlig genom att använda en array av strängreferenser istället för själva strängarna, och en ytterligare array av "bin-storlekar" som initieras vid den första passagen med antalet element i varje "bin".

Det andra och efterföljande passet utförs separat på varje korg som erhölls i det föregående passet, dela upp det i "underkorgar" och jämför de andra respektive efterföljande tecknen i strängarna.

Operationen avslutas när den maximala stränglängden uppnås eller när alla "subkorgar" har en längd på 1.

Anteckningar

Litteratur

• Donald Knuth . The Art of Computer Programming, volym 3. Sortering och sökning = The Art of Computer Programming, vol.3. Sortering och sökning. - 2:a uppl. - M . : "Williams" , 2007. - S. 192-201. — ISBN 5-8459-0082-4 .

Länkar

• Visualizer1  är en Java-applet.
• Visualizer2  är en Java-applet.
• Implementering av algoritmen i C++ Arkiverad 27 juli 2019 på Wayback Machine .