Radix -Sortierung

Ein Radix oder eine Basis ist eine Darstellung einer Zahl, die zeigt, wie viele Ziffern erforderlich sind, um eine Positionsnummer darzustellen. Um die Binärzahl beispielsweise darzustellen, beträgt der Radixwert 2 (wir repräsentieren die Binary entweder mit 0 oder 1). Um die Dezimalzahl darzustellen, beträgt der Radixwert 10 (wir stellen die Dezimalzahl mit den Zahlen 0 bis 9 dar).

Wie der Redix -Sortieralgorithmus funktioniert

Nehmen wir an, wir haben die folgende Array -Liste und möchten dieses Array mit der Radix -Sortierung sortieren:

Wir verwenden zwei weitere Konzepte in diesem Algorithmus, nämlich:

1. 1. Am wenigsten signifikante Ziffer
   2. Die wichtigste Ziffer

1. Am wenigsten signifikante Ziffer (LSD): Der Exponentwert einer Dezimalzahl, die extrem nahe am rechten Platz liegt, wird als LSD bezeichnet.

Zum Beispiel hat die Dezimalzahl "2563" den am wenigsten signifikanten Zifferwert von "3".

2. Die wichtigste Ziffer (MSD): Die MSD ist die genaue Inverse des LSD. Ein MSD-Wert ist die unzählige Ziffer der Dezimalzahl ungleich Null links in der Dezimalzahl.

Zum Beispiel hat die Dezimalzahl "2563" den bedeutendsten Zifferwert von "2".

Schritt 1: Suchen Sie nach dem wichtigsten Element (Maximalwert)

Wie wir bereits wissen, funktioniert dieser Algorithmus auf den Ziffern, um die Zahlen zu sortieren. Dafür erfordert dieser Algorithmus die maximale Anzahl von Ziffern für die Iteration. Unser erster Schritt besteht darin, die maximale Anzahl von Elementen in diesem Array herauszufinden. Nachdem wir den Höchstwert eines Arrays gefunden haben, müssen wir die Anzahl der Ziffern in dieser Zahl für die Iterationen zählen.

Schritt 2: Zählen Sie die Anzahl der Ziffern des maximalen Elements

Wir müssen die Anzahl der Ziffern des maximalen Elements eines Arrays zählen, da wir dann herausfinden können, wie viele Iterationen wir benötigen, um das Array zu sortieren.

Wie wir bereits herausgefunden haben, beträgt das maximale Element 167 und die Anzahl der Ziffern ist 3. Wir brauchen drei Iterationen, um das Array zu sortieren.

Schritt 3: Sortieren der Elemente nach der am wenigsten signifikanten Ziffer

Die erste Zifferanordnung erfolgt durch die am wenigsten signifikante Ziffer. Aus dem folgenden Bild können wir sehen, dass alle kleinsten und signifikanten Ziffern auf der linken Seite angeordnet sind. In diesem Fall konzentrieren wir uns nur auf die am wenigsten signifikante Ziffer.

Eine weitere Sache, die wir hier bemerken können, ist, dass einige Ziffern automatisch sortiert werden, auch wenn ihre Einheiten -Ziffern unterschiedlich sind, die anderen jedoch gleich sind.

Zum Beispiel, Die Nummern 36 an der Indexposition 7 und die Nummer 32 an der Indexposition 3 haben beide unterschiedliche Einheiten -Ziffern, haben jedoch die gleiche andere Zahl, was 3 ist. Offensichtlich kommt Nummer 32 vor Nummer 36. Nach den ersten Elementanordnungen können wir sehen, dass jetzt 32 vor 36 kommt, was automatisch sortiert wird.

Schritt 4: Sortieren Sie die Elemente nach der nächsten Ziffer (Zehnendigitale)

Jetzt arrangieren wir die Elemente des Arrays durch die zehnte Stelle Ziffer. Wie wir bereits wissen, muss diese Sortierung in 3 Iterationen abgeschlossen werden, da die maximale Anzahl von Elementen 3 Ziffern enthält. Dies ist unsere zweite Iteration und wir können davon ausgehen, dass die meisten Array -Elemente nach dieser Iteration sortiert werden.

Die angegebenen Ergebnisse zeigen, dass die meisten Array -Elemente bereits sortiert sind (unter 100). Wenn wir nur zwei Ziffern als maximale Zahl hatten, reichen nur zwei Iterationen aus, um das sortierte Array zu erhalten.

Schritt 5: Sortieren der Elemente auf der Grundlage der bedeutendsten Ziffer

Jetzt geben wir die dritte Iteration ein, basierend auf der bedeutendsten Ziffer (Hunderte Platz). Diese Iteration sortiert die drei stelligen Elemente des Arrays. Nach dieser Iteration sind alle Elemente des Arrays in sortierter Reihenfolge.

Nachdem wir die Elemente basierend auf der MSD arrangiert haben, ist unser Array jetzt vollständig sortiert.

Wir haben die Konzepte des Radix -Sortieralgorithmus verstanden. Aber wir brauchen einen weiteren Algorithmus, um die Radix -Sortierung zu implementieren, und das ist die Zählen Sie Sortal -Algorithmus. Lassen Sie uns das verstehen Zählen Sie Sortal -Algorithmus.

Zählen Sie Sortal -Algorithmus

Wir erläutern jetzt jeden Schritt des Zähls -Sort -Algorithmus.

Das bereitgestellte Array ist unser Eingangsarray, und die über dem Array angezeigten Zahlen sind die Indexnummern der entsprechenden Elemente.

Schritt 1: Suchen Sie das maximale Element

Der erste Schritt im Zählsartalgorithmus besteht darin, im gesamten Array nach dem maximalen Element zu suchen. Der beste Weg, um nach dem maximalen Element zu suchen.

Während des ersten Schritts stellten wir fest, dass das maximale Element 9 an der Indexposition 8 ist.

Schritt 2: Machen Sie eine neue Reihe vergleichbarer Größen

Wir erstellen eine neue Reihe ähnlicher Größen. Wie wir bereits wissen, beträgt der Höchstwert des Arrays 9. Infolgedessen benötigen wir eine maximale Array -Größe von + 1.

Wie wir im vorherigen Bild sehen können, haben wir eine Gesamtarray -Größe von 10 mit Werten von 0. Im nächsten Schritt füllen wir dieses Zählarray mit sortierten Elementen aus.

Schritt 3: Füllen Sie das neue Array nach der Frequenz jedes Elements aus

In diesem Schritt zählen wir jedes Element und füllen gemäß ihrer Frequenz die entsprechenden Werte im Array aus.

Zum Beispiel, Wie wir sehen können, ist Element 6 im Eingangsarray zweimal vorhanden. Daher geben wir den Frequenzwert von 2 unter Index 6 ein.

Schritt 4: Bestimmen Sie die kumulative Frequenz

Jetzt zählen wir die kumulative Häufigkeit des gefüllten Arrays. Diese kumulative Frequenz wird später verwendet, um das Eingangsarray zu sortieren.

Wir können die kumulative Frequenz berechnen, indem wir den aktuellen Wert zum vorherigen Indexwert hinzufügen, wie im folgenden Screenshot gezeigt:

Der letzte Wert des Arrays im kumulativen Array muss die Gesamtzahl der Elemente sein.

Schritt 5: Sortieren des Arrays nach kommutativer Frequenz

Jetzt verwenden wir das kumulative Frequenzarray, um jedes Array -Element so zuzuordnen, dass ein sortiertes Array erstellt wird.

Zum Beispiel, Das erste Element im Array 5, das wir wählen. Dann der entsprechende kumulative Frequenzwert am Index 5, der einen Wert von 7 hat. Wir verringern den Wert um 1 und haben 6. Wir platzieren den Wert 5 in den Index an der 6 -Position und verringern auch die kumulative Frequenz bei Index 5 um 1.

Die kumulative Frequenz erfolgt bei Index 5, nachdem durch eins abgelehnt wurde.

Verstehen wir dieses Konzept mit einem weiteren Beispiel.

Das nächste Element im Array ist 2. Wir wählen den Indexwert von 2 im kommutativen Frequenzarray. Wir verringern den Wert bei Index 2 und erhalten 1. Wir platzieren das Array -Element 2 an der Indexposition 1. Am Ende verringern wir den Frequenzwert bei Index 2 um 1, wie im folgenden Screenshot gezeigt:

Aus dem vorherigen sortierten Array können wir sehen, dass nur ein Platz vor 2 (Indexposition 1) und einem Wert von weniger als 2 im ursprünglichen Array bleibt, was 1 ist. Es geht also auf den richtigen Weg, um das Array zu sortieren.

Wir müssen uns nicht daran erinnern, den kumulativen Wert bei jeder Iteration zu verringern. Nach zwei der vorherigen Iterationen sieht das kumulative Array aus wie folgt:

Schritt 6: Final Array

Wir führen den Schritt 5 aus, bis alle Array -Elemente in dem sortierten Array gefüllt sind. Nachdem es gefüllt ist, sieht unser Array so aus:

C ++ - Programm für den Radix -Sortieralgorithmus

Dieses Beispiel basiert auf der Erklärung in diesem Linux -Hinweis -Tutorial

#enthalten
Verwenden von Namespace STD;
void radixsortalgo (int a [], int size_of_a)
// Im ersten Schritt (Schritt 1) ​​finanzieren wir den Maximalwert im Array.
int maximumnumber = a [0];
für (int i = 1; imaximumnumber = max (maximumnumber, a [i]);

// Im zweiten Schritt (Schritt 2) berechnen wir die Anzahl der Ziffern von
// Das maximale Element des Arrays
int digitsCount = 0;
while (maximumnumber> 0)
DigitsCount ++;
Maximumnum /= 10;

// Wir aktualisieren jetzt ein neues Array (Schritte 3,4 und 5)
für (int i = 0; iint pwr = pow (10, i);
int new_a [size_of_a];
// Dies ist ein count_array, das für das Zählarray verwendet wird
// Ziffern 0 bis 9 sortieren.
int count_array [10];
memset (count_array, 0, sizeof (count_array));
// Berechnung der Frequenz jedes Elements des Arrays
für (int j = 0; jint num = (a [j]/pwr) % 10;
count_array [num] ++;

// Dies ist eine komulative Frequenz
für (int j = 1; j<10;j++)
count_array [j] += count_array [j-1];

// Wir machen das Frequenzarray mit jedem Element zuordnen
// des Arrays, um die gewünschte Position im aktualisierten Array herauszufinden
für (int j = size_of_a-1; j> = 0; j-)
int num = (a [j]/pwr) % 10;
new_a [count_array [num] -1] = a [j];
count_array [num]-;

// Jetzt aktualisieren wir das Array mit dem Neuarray
für (int j = 0; ja [j] = new_a [j];

// Schließlich drucken wir das sortierte Array -Ergebnis
für (int j = 0; jCout<Cout<
int main ()
// Dieses Wertearray wird mit dem Radix -Sortieralgorithmus sortiert.
int a [] = 155, 10, 51, 38, 16, 811, 755, 3, 91, 6;
// Wir berechnen die Größe des Arrays
int size_of_a = sizeof (a)/sizeof (size_of_a);
// Aufrufen zur Radix -Sortieralgorithmusmethode
radixsortalgo (a, size_of_a);
Rückkehr 1;

Ausgabe aus dem Ausführen von C+ Radix -Sortierung

LinuxHint@Desktop: ~ $ ./Radix
3 6 10 16 38 51 91 155 755 811
LinuxHint@Desktop: ~ $

Zeitkomplexität des Radix -Sortieralgorithmus

Berechnen wir die Zeitkomplexität des Radix -Sortieralgorithmus.

Schritt 1: Um die maximale Anzahl von Elementen im gesamten Array zu berechnen, durchqueren wir das gesamte Array. Die erforderliche Gesamtzeit ist also O (n).

Schritt 2: Nehmen wir an, dass die Gesamtstellen in der maximalen Zahl k sind. Die Gesamtzeit, die benötigt wird, um die Anzahl der Ziffern in einer maximalen Zahl zu berechnen, ist O (k).

Schritte 3 bis 5: Diese Schritte funktionieren selbst an den Ziffern selbst, so dass sie O (k) Zeiten nehmen, zusammen mit dem Zählen des Sortieralgorithmus bei jeder Iteration - o (k * n).

Infolgedessen ist die Gesamtzeitkomplexität O (K * n).

Abschluss

Wir haben die Radix -Sortier- und Zählalgorithmus untersucht. Es gibt verschiedene Arten von Sortieralgorithmen, die auf dem Markt verfügbar sind. Der beste Algorithmus hängt auch von den Anforderungen ab. Es ist nicht leicht zu sagen, welcher Algorithmus am besten ist. Aufgrund der Zeitkomplexität versuchen wir jedoch, den besten Algorithmus herauszufinden. Und auf der Grundlage davon ist die Radix -Sortierung auch einer der besten Algorithmen zum Sortieren.