DAA - Tri Radix

Radix sortest une petite méthode que de nombreuses personnes utilisent intuitivement lors de l'alphabétisation d'une grande liste de noms. Plus précisément, la liste des noms est d'abord triée en fonction de la première lettre de chaque nom, c'est-à-dire que les noms sont organisés en 26 classes.

Intuitivement, on peut vouloir trier les nombres sur leur chiffre le plus significatif. Cependant, le tri Radix fonctionne de manière contre-intuitive en triant d'abord les chiffres les moins significatifs. Lors du premier passage, tous les nombres sont triés sur le chiffre le moins significatif et combinés dans un tableau. Ensuite, au deuxième passage, les nombres entiers sont à nouveau triés sur les deuxièmes chiffres les moins significatifs et combinés dans un tableau et ainsi de suite.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Une analyse

Chaque touche est regardée une fois pour chaque chiffre (ou lettre si les touches sont alphabétiques) de la touche la plus longue. Par conséquent, si la clé la plus longue am chiffres et il y a n clés, le tri de base a un ordre O(m.n).

Cependant, si nous regardons ces deux valeurs, la taille des clés sera relativement petite par rapport au nombre de clés. Par exemple, si nous avons des clés à six chiffres, nous pourrions avoir un million d'enregistrements différents.

Ici, on voit que la taille des clés n'est pas significative, et cet algorithme est de complexité linéaire O(n).

Exemple

L'exemple suivant montre comment le tri Radix fonctionne sur sept nombres à 3 chiffres.

Contribution	1 er col	2 ème passage	3 ème passage
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

Dans l'exemple ci-dessus, la première colonne est l'entrée. Les colonnes restantes affichent la liste après des tris successifs sur des positions de chiffres de plus en plus significatives. Le code pour le tri Radix suppose que chaque élément d'un tableauA de n éléments a d chiffres, où chiffre 1 est le chiffre le plus bas et d est le chiffre d'ordre le plus élevé.