WikiDer > Radix sortieren

Radix sortieren ist ein Sortieralgorithmus die in der Lage ist, Sammlungen bestimmter Elemente zu sortieren. Radix sort verwendet eine Kombination aus einer festen Sortierstrategie und einem separaten zweiten Sortieralgorithmus (einem Hilfsalgorithmus), um einen bestimmten Satz von Elementen zu sortieren. Radix sort kann je nach verwendetem Hilfsalgorithmus sehr effizient beim Sortieren einer Sammlung sein.

Die Input-Sammlung

Einer der Gründe dafür, dass Radix-Sort besonders effizient durchgeführt werden kann, liegt darin, dass Radix-Sort im Prinzip nicht allgemein anwendbar ist. Radix-Sort geht davon aus, dass die zu sortierenden Elemente Zahlen sind oder zumindest Elemente, die Zahlen in ihrer Struktur ähneln -- genauer gesagt sortiert Radix-Sort Elemente, die aus kartesischen Produkten einer endlichen Menge V bestehen, mit sich selbst, wobei a Gesamtbestellung auf V definiert ist, und dieselbe Ordnung wird nach Bedeutung auf das gesamte kartesische Produkt ausgedehnt.

Beispiele für Mengen, die mit Radix-Sort geordnet werden können, sind natürliche Zahlen und Buchstabenfolgen einer bestimmten Länge. Nehmen wir zum Beispiel die natürlichen Zahlen, die aus fünf Ziffern bestehen, können wir eine solche Zahl als Element des kartesischen Produkts betrachten ${displaystyle Vimes Vimes Vimes Vimes V}$, mit ${Anzeigestil V={0,1,2,3,4,5,6,7,8,9}}$. Hierin existiert eine Ordnung auf V (0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9) die sich der Bedeutung nach auf die fünfstelligen natürlichen Zahlen (0xxxx < 5xxxx < 9xxxx, A2xxx < A4xxx usw. ). Radix sort verwendet diese Struktur, um Elemente zu sortieren.

Übrigens kann Radix-Sort in der Tat auf allgemeine Mengen angewendet werden, wenn zuerst ein Bild von dieser Menge auf die natürlichen Zahlen definiert wird.

Der Algorithmus

Angenommen, wir haben eine Menge von Elementen (A) mit einer Struktur wie oben beschrieben -- ohne Einschränkung der Allgemeinheit nehmen wir an, dass es sich um Zahlen handelt. Dann können wir die Elemente wie folgt anordnen:

1. Beginnen Sie auf einer Seite (die höchstwertige oder die niedrigste Ziffer); betrachte nur diese Zahl
2. Bestellen Sie die Kollektion nur nach dieser Nummer
3. Innerhalb der nun gefundenen Bestellung bestellst du auf der nächsten Nummer
4. Mach weiter, bis du alle Zahlen hast
5. Jetzt ist A komplett geordnet

Radix sort ist der Algorithmus, der die obigen Schritte ausführt, beginnend mit dem am wenigsten bedeutende Ziffer.

Um die obigen Schritte auszuführen, verwendet radix sort eindeutig die Struktur des zu sortierenden Sets. Radixsort benötigt aber auch einen Hilfsalgorithmus, um A nach einer Ziffer der gesamten Ziffernreihe zu sortieren. Dieser Algorithmus muss stabil sein:

• Sei M ein Sortieralgorithmus.
• Sei V(M) die nach M geordnete Menge der Elemente.
• Seien v0 und v1 Elemente von V.
• Sei idy(v) die Position von v in V vor der Anwendung von M.
• Sei sidy(v) die Position von v in V nach Anwendung von M.
• Sei Q(v) die Funktion, die einen Wert für v zurückgibt; M sortiert V nach der Größe von Q(v) für jedes v in V.

Dann M stabil wenn ${displaystyle idy(v_{0})$dh wenn die Bewertung von v0 und v1 für M gleich ist, dann bleiben v0 und v1 vor und nach der Anwendung von M relativ zueinander in der gleichen Reihenfolge.

Die Stabilität des Hilfsalgorithmus ist für die Radixsortierung von entscheidender Bedeutung. Radix sort sortiert eine Reihe von Zahlen immer eine Ziffer nach der anderen - aber es nutzt definitiv die Stabilität des Hilfsalgorithmus, da die Sortierung nach vorherigen Ziffern beim Sortieren nach der nächsten Ziffer beibehalten wird. Daher wird die Menge A in ihrer Gesamtheit geordnet, nachdem sie nach der höchstwertigen Stelle geordnet wurde.

Schauen wir uns ein Beispiel an:

(A) (B) (C) (D)329 720 720 329457 355 329 355657 436 436 436839 → 457 → 839 → 457436 657 355 657720 329 457 720355 839 657 839

(Eine zufällige
(B) A wird nach der letzten Ziffer sortiert
(C) B wird nach der mittleren Ziffer sortiert
(D) C ist nach der ersten Ziffer sortiert

Beachten Sie, dass im obigen Beispiel die Spaltennummer i nach den letzten i-Ziffern richtig angeordnet ist. Wenn wir die dritte Spalte (Nummer 2) von links nehmen und die erste Ziffer ignorieren, ist sofort klar, dass die Spalte nach den letzten beiden Ziffern richtig geordnet ist. Die Stabilität des Hilfsalgorithmus sorgt dafür, dass diese "Interordering" erhalten bleibt, sobald auch die nächste Ziffer geordnet wird.

Beachten Sie auch, dass das Sortieren viel mehr Aufwand gekostet hätte, wenn wir vom wichtigsten zum am wenigsten sortiert hätten. Bei dieser Ordnung ist Stabilität keine ausreichende Voraussetzung für den Hilfsalgorithmus -- anstatt die relative Ordnung zweier Elemente gleicher Ordnung beizubehalten, müssen wir beim Ordnen vom höchsten zum am wenigsten signifikanten sogar die ganze Halten Sie die Ordnung zwischen den Schritten zusammen. Das würde bedeuten, dass wir in jedem Schritt die Menge A in Stücke mit den gleichen n Ziffern auf der linken Seite teilen und diese Stücke intern separat sortieren müssten.

Formaler Nachweis der Richtigkeit der Radixsortierung

Der klassische Korrektheitsbeweis für die Radixsortierung erfolgt mittels volle Einweisung auf die Anzahl der Stellen n der Elemente der zu ordnenden Menge.

Base

Sei n = 0. Für diesen Fall ist die Radixsortierung richtig: Die leere Menge ist per Definition geordnet.

Induktionshypothese

Das Anwenden der Radixsortierung auf einen Satz von Zahlen der Länge N ordnet den Satz korrekt.

Schritt

Sei n = N 1. Dann kann Radix-Sort n-mal angewendet werden und die Menge ist gemäß der Induktionshypothese korrekt auf die n niederwertigsten Stellen geordnet. Wenden wir nun den Hilfsalgorithmus auf die n 1., höchstwertige Ziffer C an. Für jedes Paar der Elemente A und B der Menge gibt es nun zwei Möglichkeiten:

• ${Anzeigestil C_{A}$ (oder umgekehrt). In diesem Fall (wegen der Korrektheit des Hilfsalgorithmus) werden A und B so geordnet, dass A vor B kommt, was richtig ist, weil ${Anzeigestil C_{A}$.
• ${Displaystil C_{A}=C_{B}}$. Da die höchstwertige Ziffer nicht zwischen A und B unterscheidet, waren A und B bereits gut abgeglichen – sie waren bereits nach ihren weniger signifikanten Ziffern geordnet. Da der Hilfsalgorithmus stabil ist, bleibt ihre relative Reihenfolge erhalten und auch in diesem Fall ist die Radixsortierung korrekt.

Radix sortieren im Code

Im Allgemeinen sieht die Radixsortierung so aus:

|[constein:SammlungvonnatürlichZahlen;d:ganze Zahl;{d = die Anzahl der Stellen in jedem Element von A}varnein:ganze Zahl;|nein:=1;tunnein<=d->SortiereneinzuZahlNummerneinmiteinstabilHilfsalgorithmusod]|

Die Effizienz von Radixsort

Um Zahlen von d Ziffern zu sortieren, werden d Aufrufe des Hilfsalgorithmus benötigt. Dies macht die Effizienz von Radixsort ${displaystyle mathbb {O} (dK)}$, mit K die Effizienz des Hilfsalgorithmus. Ist dieser Hilfsalgorithmus linear (wie bei Zählen sortieren möglich), dann ist auch die Radixsortierung linear.

Der Name Radixsort

Radix sort wurde häufig in Lochkartensortiermaschinen verwendet. Der "Hilfsalgorithmus" von Radix sort bestand hier darin, den Wert dieser Ziffer für jede gestanzte Ziffer zu prüfen und dann die Karte in ein entsprechendes Fach zu legen. Radix sort selbst bestand dann darin, die Karten aus verschiedenen Fächern in der richtigen Reihenfolge zusammenzufassen und wieder auf die Fächer bis zur nächsten Nummer aufzuteilen.

Diese Methode erforderte genau so viele Container, wie es Zahlen gab, mit denen Zahlen gemacht werden konnten - diese Zahl wird als Radix wenn es Base eines Zahlensystems. Daher Radixsortierung.

Ein Codebeispiel

Der folgende Code ist eine Demonstrationsimplementierung von radix sort in Pascal. Dieses Programm liest aus der Standardeingabe eine Datei mit einer Zahl pro Zeile -- die erste Zahl die Anzahl der Stellen der anderen Zahlen, die restlichen Zahlen die zu sortierende Menge.

Die gegebene Implementierung simuliert die oben erwähnten Sortiermaschinen, wobei die Tray-Methode als Hilfsalgorithmus verwendet wird.

Programmradix_demo;{$R-,ich}Verfahrenradixsort(varTermine:Arrayoderganze Zahl;Dezimalstellen:ganze Zahl);constRADIX=10;{Benutze das Dezimalsystem.}ArtPbak=^Behälter;Behälter=Array[1..1]oderganze Zahl;varBacken:Array[0..RADIX-1]oderPbak;backen_theke:Array[0..RADIX-1]oderganze Zahl;Dividende:ganze Zahl;Verfahrensort_position(Position:ganze Zahl);{Gehen Sie durch die Daten und sortieren Sie sie nach der angegebenen Position. Sortiere das erfolgt, indem die Datenelemente in die Bins gelegt werden. Danach ist die Bins nacheinander abgeschlossen und Inhalt an Daten-Arrayaar . zurückgegeben Erstellen einer sortierten Liste.}varich,ja,p,temp:ganze Zahl;loslegen{Leeren Sie die Behälter.}zumich:=0zuRADIX-1tunbacken_theke[ich]:=0;{Lege die Datteln in die Behälter.}zumich:=niedrig(Termine)zuhoch(Termine)tunloslegentemp:=(Termine[ich]divDividende)modRADIX;inc(backen_theke[temp]);Backen[temp]^[backen_theke[temp]]:=Termine[ich];Ende;Dividende:=Dividende*RADIX;{Setzen Sie den Inhalt der Bins zurück in die Daten.}p:=niedrig(Termine);zumich:=0zuRADIX-1tunzumja:=1zubacken_theke[ich]tunloslegenTermine[p]:=Backen[ich]^[ja];inc(p);Ende;Ende;varich:ganze Zahl;loslegen{Dividende initialisieren.}Dividende:=1;{Erstelle die Behälter. Die extremste Situation ist, dass alle Datenelemente landen in 1 Tonne. Das ist also die angeforderte Speichermenge.}zumich:=0zuRADIX-1tungetmem(Backen[ich],(1hoch(Termine)-niedrig(Termine))*Größe von(ganze Zahl));zumich:=1zuDezimalstellentunsort_position(ich);{Brechen Sie die Behälter auf.}zumich:=0zuRADIX-1tunFreemem(Backen[ich],(1hoch(Termine)-niedrig(Termine))*Größe von(ganze Zahl));Ende;{DEMO: Das folgende Hauptprogramm liest aus der Standardeingabe: - Die Anzahl der Nachkommastellen - Die Anzahl der zu sortierenden Zahlen - Die zu sortierenden Zahlen selbst. Die Standardausgabe gibt die sortierte Liste aus.}varTermine:Arrayoderganze Zahl;Zahl_Zahlen,Dezimalstellen,ich,X:ganze Zahl;loslegenlesen(Dezimalstellen);lesen(Zahl_Zahlen);Setlänge(Termine,Zahl_Zahlen);zumich:=0zuZahl_Zahlen-1tunlesen(Termine[ich]);radixsort(Termine,Dezimalstellen);{Sortierung starten}zumich:=niedrig(Termine)zuhoch(Termine)tunschreiben(Termine[ich]);Ende.