Radix-Sortieralgorithmus

In diesem Tutorial erfahren Sie, wie die Radix-Sortierung funktioniert. Außerdem finden Sie Arbeitsbeispiele für die Radix-Sortierung in C, C ++, Java und Python.

Die Radix-Sortierung ist eine Sortiertechnik, bei der die Elemente sortiert werden, indem zuerst die einzelnen Ziffern desselben Stellenwerts gruppiert werden . Sortieren Sie dann die Elemente nach ihrer aufsteigenden / abnehmenden Reihenfolge.

Angenommen, wir haben ein Array von 8 Elementen. Zuerst sortieren wir Elemente basierend auf dem Wert der Einheitsstelle. Dann werden wir Elemente basierend auf dem Wert des zehnten Platzes sortieren. Dieser Prozess dauert bis zum letzten wichtigen Ort.

Das anfängliche Array sei (121, 432, 564, 23, 1, 45, 788). Es ist nach Radix-Sortierung sortiert, wie in der folgenden Abbildung gezeigt.

Arbeiten von Radix Sort

Bitte gehen Sie die Zählsortierung durch, bevor Sie diesen Artikel lesen, da die Zählsortierung als Zwischensortierung in der Radix-Sortierung verwendet wird.

Wie funktioniert Radix Sort?

  1. Finden Sie das größte Element im Array, dh max. Sei Xdie Anzahl der Ziffern in max. Xwird berechnet, weil wir alle wichtigen Stellen aller Elemente durchlaufen müssen.
    In diesem Array (121, 432, 564, 23, 1, 45, 788)haben wir die größte Zahl 788. Es hat 3 Ziffern. Daher sollte die Schleife bis zu Hunderten Stellen (dreimal) reichen.
  2. Gehen Sie nun jeden wichtigen Ort einzeln durch.
    Verwenden Sie eine stabile Sortiertechnik, um die Ziffern an jeder wichtigen Stelle zu sortieren. Wir haben dafür die Zählsortierung verwendet.
    Sortieren Sie die Elemente anhand der Ziffern der Einheitsstelle ( X=0). Verwenden der Zählsortierung zum Sortieren von Elementen basierend auf dem Ort der Einheit
  3. Sortieren Sie nun die Elemente anhand der Ziffern an der Zehnerstelle. Sortieren Sie die Elemente nach der Zehnerstelle
  4. Schließlich sortieren Sie die Elemente basierend auf den Ziffern an Hunderten. Sortieren Sie Elemente nach Hunderten von Stellen

Radix-Sortieralgorithmus

 radixSort (Array) d <- maximale Anzahl von Ziffern im größten Element Erstellen Sie d Buckets der Größe 0-9 für i <- 0, um die Elemente nach den i-ten Stellen zu sortieren, indem Sie countSort zählenSort (Array, d) max <- find Das größte Element unter den Elementen an der d-ten Stelle initialisiert das Zählarray mit allen Nullen für j <- 0, um die Gesamtanzahl jeder eindeutigen Ziffer an der d-ten Stelle der Elemente zu ermitteln, und speichert die Zählung am j-ten Index im Zählarray für i <- 1 bis max find Die kumulative Summe und die Speicherung im Zählarray selbst für j <- Größe bis 1 stellen die Elemente wieder her, um die Anzahl jedes wiederhergestellten Elements um 1 zu verringern

Beispiele für Python, Java und C / C ++

Python Java C C ++ 
 # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = (0) * size count = (0) * 10 # Calculate count of elements for i in range(0, size): index = array(i) // place count(index % 10) += 1 # Calculate cummulative count for i in range(1, 10): count(i) += count(i - 1) # Place the elements in sorted order i = size - 1 while i>= 0: index = array(i) // place output(count(index % 10) - 1) = array(i) count(index % 10) -= 1 i -= 1 for i in range(0, size): array(i) = output(i) # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place> 0: countingSort(array, place) place *= 10 data = (121, 432, 564, 23, 1, 45, 788) radixSort(data) print(data) 
 // Radix Sort in Java Programming import java.util.Arrays; class RadixSort ( // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int() output = new int(size + 1); int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i < size; i++) array(i) = output(i); ) // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Main function to implement radix sort void radixSort(int array(), int size) ( // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place> 0; place *= 10) countingSort(array, size, place); ) // Driver code public static void main(String args()) ( int() data = ( 121, 432, 564, 23, 1, 45, 788 ); int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Radix Sort in C Programming #include // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int output(size + 1); int max = (array(0) / place) % 10; for (int i = 1; i max) max = array(i); ) int count(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
 // Radix Sort in C++ Programming #include using namespace std; // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( const int max = 10; int output(size); int count(max); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i  = 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )

Komplexität

Da die Radix-Sortierung ein nicht vergleichender Algorithmus ist, hat sie Vorteile gegenüber vergleichenden Sortieralgorithmen.

Für die Radix-Sortierung, bei der die Zählsortierung als stabile Zwischensortierung verwendet wird, beträgt die zeitliche Komplexität O(d(n+k)).

Hier dist der Zahlenzyklus und O(n+k)die zeitliche Komplexität der Zählsortierung.

Somit weist die Radix-Sortierung eine lineare Zeitkomplexität auf, die besser ist als O(nlog n)bei vergleichenden Sortieralgorithmen.

Wenn wir sehr große Ziffern oder die Anzahl anderer Basen wie 32-Bit- und 64-Bit-Zahlen verwenden, kann dies in linearer Zeit erfolgen, die Zwischensortierung nimmt jedoch viel Platz ein.

Dies macht den Radix-Sortierraum ineffizient. Dies ist der Grund, warum diese Sortierung in Softwarebibliotheken nicht verwendet wird.

Radix-Sortieranwendungen

Radix-Sortierung ist in implementiert

  • DC3-Algorithmus (Kärkkäinen-Sanders-Burkhardt) beim Erstellen eines Suffix-Arrays.
  • Orte, an denen es Zahlen in großen Bereichen gibt.

Interessante Beiträge...