Le tri par seau et le tri radix sont des cousins proches ; le tri par seau va du MSD au LSD, tandis que le tri radix peut aller dans les deux "directions" (LSD ou MSD). Comment fonctionnent ces deux algorithmes et, en particulier, quelles sont leurs différences ?
Réponses
Trop de publicités?
Akash
Points
451
Le passage initial des deux RadixSort y BucketSort est exactement le même. Les éléments sont mis dans buckets (o bins ) de plages incrémentales (par exemple 0-10, 11-20, ... 90-100), en fonction du nombre de chiffres du plus grand nombre.
Au prochain passage, cependant, BucketSort ordonne ces "seaux" et les ajoute à un tableau. Cependant, RadixSort ajoute les bacs sans les trier davantage et les "remet dans le bac" sur la base du deuxième chiffre (position des dizaines) des nombres. Par conséquent, BucketSort est plus efficace pour les tableaux " denses ", tandis que RadixSort peut gérer les tableaux épars (enfin, pas exactement épars, mais espacés).
dev_ankit
Points
486
Bucket Sort et Radix Sort sont comme des algorithmes de tri jumeaux car ce ne sont pas des tris par comparaison et l'idée générale est similaire. En outre, ils sont tous deux un peu abstraits dans leur mise en œuvre.
Radix Sort :
-
Radix signifie base (binaire, octal, décimal, etc.). Par conséquent, ce tri est destiné aux nombres (également utilisé pour les chaînes de caractères). Cela fonctionne lorsque chaque élément E est comme e k ...e 2 e 1 e 0 où e i est dans une certaine fourchette. (généralement 0 à une base comme 0-9 en décimal ou 0-255 en caractères ASCII)
-
Il utilise ensuite k passages d'un algorithme de sous-tri stable (It doit être stable sinon le tri Radix ne fonctionnera pas) pour trier les nombres. Cet algorithme de tri secondaire est généralement appelé Counting sort ou Bucket sort, mais il ne peut s'agir d'un tri Radix .
-
Vous pouvez commencer par le chiffre le plus significatif ou le chiffre le moins significatif car il mélange tous les numéros à chaque passage (de k à 0 ou de 0 à k)
-
Il s'agit d'un stable algorithme de tri.
Triage des seaux :
-
Il sépare le tableau en des groupes plus petits ou des seaux et les trie individuellement en utilisant un algorithme de sous-tri ou un appel récursif à lui-même, puis combine le résultat . Par exemple, trier les joueurs en les ajoutant dans les cases de leur équipe, puis les trier en fonction de leur numéro de maillot ou quelque chose comme trier les numéros de 1 à 30 dans 3 cases de 1 à 10, 11 à 20 et 21 à 30.
-
En l'étape de la combinaison est simple (contrairement au tri par fusion). Il suffit de recopier les éléments de chaque seau dans le tableau d'origine ou de joindre la tête de chaque seau à la queue du seau précédent (dans le cas de listes chaînées).
-
Le radix/base pourrait être un type/instance du groupe/seau tout en triant les chiffres. Par conséquent, vous pouvez considérer MSD radix comme une instance modifiée du tri par seau.
-
Le tri des seaux est pas en place mais stable algorithme de tri. Toutefois, certaines variantes du tri par seau peuvent ne pas être stables (si vous utilisez un algorithme de tri secondaire qui n'est pas stable).
