radix sort

Radix-Sortierung – Basissortierung. Der Algorithmus ähnelt der Zählsortierung darin, dass es keinen Vergleich von Elementen gibt; stattdessen werden Elemente *Zeichen für Zeichen* in *Buckets* (Buckets) gruppiert, der Bucket wird anhand des Index des aktuellen Zahlenzeichens ausgewählt. Zeitkomplexität – O(nd).

Es funktioniert ungefähr so:

Die Eingabe erfolgt aus den Zahlen 6, 12, 44, 9
Wir werden 10 Buckets mit Listen (0-9) erstellen, in die wir Zahlen Stück für Stück hinzufügen/sortieren.

Weiter:

Starten Sie eine Schleife mit Zähler i bis zur maximalen Anzahl von Zeichen in der Zahl
Durch den Index i von rechts nach links erhalten wir ein Symbol für jede Zahl; wenn es kein Symbol gibt, dann gehen wir davon aus, dass es Null ist
Konvertieren Sie das Symbol in eine Zahl
Wählen Sie einen Bucket nach Indexnummer aus und geben Sie dort die ganze Zahl ein
Nachdem Sie mit der Suche durch die Zahlen fertig sind, wandeln Sie alle Buckets wieder in eine Zahlenliste um
Erhalten Sie Zahlen nach Rang sortiert
Wiederholen Sie den Vorgang, bis alle Ziffern verschwunden sind

Beispiel für Radix-Sortierung in Scala:


import scala.util.Random.nextInt



object RadixSort {

    def main(args: Array[String]) = {

        var maxNumber = 200

        var numbersCount = 30

        var maxLength = maxNumber.toString.length() - 1



        var referenceNumbers = LazyList.continually(nextInt(maxNumber + 1)).take(numbersCount).toList

        var numbers = referenceNumbers

        

        var buckets = List.fill(10)(ListBuffer[Int]())



        for( i <- 0 to maxLength) { numbers.foreach( number => {

                    var numberString = number.toString

                    if (numberString.length() > i) {

                        var index = numberString.length() - i - 1

                        var character = numberString.charAt(index).toString

                        var characterInteger = character.toInt  

                        buckets.apply(characterInteger) += number

                    }

                    else {

                        buckets.apply(0) += number

                    }

                }

            )

            numbers = buckets.flatten

            buckets.foreach(x => x.clear())

        }

        println(referenceNumbers)

        println(numbers)

        println(s"Validation result: ${numbers == referenceNumbers.sorted}")

    }

}

Der Algorithmus verfügt auch über eine Version zur parallelen Ausführung, beispielsweise auf einer GPU; Es gibt auch eine Möglichkeit zum Sortieren von Bits, die sehr interessant und wirklich atemberaubend sein muss!