radix sort

Tri Radix – tri par base. L’algorithme est similaire au tri par comptage dans la mesure où il n’y a pas de comparaison des éléments ; à la place, les éléments sont regroupés *caractère par caractère* dans des *buckets* (buckets), le bucket est sélectionné par l’index du numéro-caractère actuel. Complexité temporelle – O(nd).

Cela fonctionne comme ceci :

L’entrée sera les nombres 6, 12, 44, 9
Nous allons créer 10 groupes de listes (0 à 9), dans lesquels nous ajouterons/trierons des nombres petit à petit.

Démarrer une boucle avec le compteur i jusqu’au nombre maximum de caractères du nombre
Par l’index i de droite à gauche, nous obtenons un symbole pour chaque nombre ; s’il n’y a pas de symbole, alors nous supposons qu’il est nul
Convertir le symbole en nombre
Sélectionnez un bucket par numéro d’index et insérez-y le numéro entier
Après avoir terminé la recherche parmi les nombres, reconvertissez tous les compartiments en une liste de nombres
Obtenir des chiffres triés par rang
Répétez jusqu’à ce que tous les chiffres aient disparu

Exemple de tri Radix dans 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}")

    }

}

L’algorithme dispose également d’une version pour une exécution parallèle, par exemple sur un GPU ; Il y a aussi une petite option de tri, qui doit êtretrès intéressante et vraiment époustouflante !