Radix sortering

radix sortering
Forfatter	Hollerith, Herman
formål	Sorteringsalgoritme
Datastruktur	array
værste tid	, hvor w er antallet af bits, der kræves for at lagre hver nøgle.
Hukommelsesomkostninger
Mediefiler på Wikimedia Commons

Bitwise sortering ( eng.  radix sort ) er en sorteringsalgoritme , der kører i lineær tid. Der er stabile muligheder.

Algoritme

Oprindeligt beregnet til sortering af heltal skrevet som cifre. Men da enhver information i computeres hukommelse registreres som heltal, er algoritmen egnet til at sortere alle objekter, hvis registrering kan opdeles i "cifre", der indeholder sammenlignelige værdier. For eksempel kan du på denne måde sortere ikke kun tal skrevet som et sæt tal, men også strenge, der er et sæt tegn, og generelt vilkårlige værdier i hukommelsen, repræsenteret som et sæt bytes.

Sammenligningen udføres bit for bit: først sammenlignes værdierne af et ekstremt ciffer, og elementerne grupperes i henhold til resultaterne af denne sammenligning, derefter sammenlignes værdierne af det næste ciffer, tilstødende, og elementerne er enten ordnet efter resultaterne af sammenligning af værdierne af dette ciffer inden for grupperne dannet i det foregående pass, eller omarrangeret som en helhed, men bevarer den relative rækkefølge opnået ved den tidligere sortering. Så gøres det samme til næste udledning, og så fortsætter man til det sidste.

Da det er muligt at justere de sammenlignede poster i forhold til hinanden i forskellige retninger, er der i praksis to muligheder for denne sortering. For tal kaldes de i form af betydningen af ​​cifrene i nummeret, og det viser sig sådan her: du kan justere indtastningerne af tal mod mindre signifikante cifre (på højre side, mod etere, mindst signifikante ciffer, LSD ) eller mere signifikante cifre (i venstre side, fra mere signifikante cifre, mest signifikante cifre, MSD).

Med LSD-sortering (sortering med justering efter det mindst signifikante ciffer, til højre, til enere) opnås den rækkefølge, der er passende for tal. For eksempel: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. Det vil sige, at her sorteres værdierne først efter enere, derefter sorteret efter tiere, og holder sorteringen efter et inde tiere, derefter i hundrede, holde sortering efter tiere og enheder inden for hundreder osv.

MSD-sortering (høj orden, venstrejusteret) resulterer i alfabetisk rækkefølge, som er passende til sortering af tekstlinjer. For eksempel vil "b, c, d, e, f, g, h, i, j, ba" sortere som "b, ba, c, d, e, f, g, h, i, j". Hvis MSD anvendes på tallene i eksemplet, får vi rækkefølgen 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Du kan akkumulere information om grupper ved hvert pas på forskellige måder - for eksempel i lister, i træer, i arrays, udskrivning af enten selve elementerne eller deres indekser osv.

Der er en ustabil version af rekursiv bitvis sortering, som udføres direkte i det sorterede array: ved den første passage går bevægelsen mod hinanden, i begyndelsen af ​​arrayet søges et element med 1 i det første bitciffer, i slutningen af ​​arrayet søges et element med 0 i samme ciffer. De fundne elementer ombyttes, og så videre, indtil de pågældende indekser mødes. I begyndelsen af ​​arrayet, før indeksenes mødepunkt, samles således alle elementer med en bit lig med 0, og efter dette indeks alle elementer med en bit lig med 1. Så kan man rekursivt fuldstændig på samme måde. iterere gennem de resulterende underområder af arrayet, sammenligne værdierne af den anden og efterfølgende bit, og omarrangere elementernes steder.

Ansøgning om rækker i kurvsorteringsvarianten

Kurvsortering kan bruges til at sortere efter rang . Hver kategori køres to gange. Ved det første gennemløb tælles antallet af visse værdier i denne kategori. Derefter forberedes arrays for hver mulig værdi til at gemme elementerne med denne værdi. I løbet af den anden omgang bliver selve elementerne skrevet ud til disse arrays. En effektiv implementering er mulig ved at bruge et array af strengreferencer i stedet for strengene selv, og et ekstra array af "bin-størrelser" initialiseret ved den første passage med antallet af elementer i hver "bin".

Den anden og efterfølgende gennemgang udføres separat på hver kurv opnået i det foregående gennemløb, idet den opdeles i "underkurve" og sammenlignes henholdsvis den anden og de efterfølgende tegn i strengene.

Operationen slutter, når den maksimale strenglængde er nået, eller når alle "underkurve" har en længde på 1.

Noter

Litteratur

• Donald Knuth . The Art of Computer Programming, bind 3. Sortering og søgning = The Art of Computer Programming, vol.3. Sortering og søgning. - 2. udg. - M . : "Williams" , 2007. - S. 192-201. — ISBN 5-8459-0082-4 .

Links

• Visualizer1  er en Java-applet.
• Visualizer2  er en Java-applet.
• Implementering af algoritmen i C++ Arkiveret 27. juli 2019 på Wayback Machine .