Quelle est la différence entre le seau de tri et tri radix?

la passe initiale de RadixSort et BucketSort est exactement la même. Les éléments sont mis dans buckets (ou bins ) des gammes incrémentielles (par exemple 0-10, 11-20, ... 90-100), selon le nombre de chiffres dans le plus grand nombre.

Dans le passage suivant, cependant, BucketSort les commandes jusqu'ces "seaux" et ajoute-les dans un tableau. Cependant, RadixSort Ajoute les seaux sans les trier davantage et "re-seaux" il basé sur la seconde chiffres (dix) chiffres. Par conséquent, BucketSort est plus efficace pour les réseaux "denses", tandis que RadixSort peut bien gérer les réseaux épars (Eh bien, pas exactement épars, mais espacés).

Bucket Sort et Radix Sort sont comme des algorithmes de tri de soeur parce qu'ils ne sont pas des sortes de comparaison et l'idée générale est similaire. Aussi, ils sont un peu abstrait dans la mise en œuvre.

Radix Sort :

• Radix signifie base (binaire, octale, décimale,etc.). Par conséquent, ce tri est pour les nombres (également utilisée pour les chaînes). Cela fonctionne quand chaque élément E est comme e _k ...e ₂ e ₁ e ₀ , où e _je est dans une certaine gamme. (habituellement 0 à une base comme 0-9 en décimal ou 0-255 en caractères ASCII)

• il utilise ensuite k passes d'un algorithme de sous-tri stable (il doit être stable sinon le tri Radix ne fonctionnera pas) pour trier les nombres. Cet algorithme de sous-tri est généralement il ne peut pas être le tri Radix lui-même .

• vous pouvez commencer par le chiffre le plus significatif ou le chiffre le moins significatif parce que il mélange tous les nombres dans chaque passe (de k à 0 ou 0 à k)

• il s'agit d'un algorithme de tri stable .

Seau De Tri:

• il sépare le tableau en plus petits groupes ou seaux et les trie individuellement en utilisant un algorithme de sous-tri ou appel récursif à lui-même et puis combine le résultat . Par exemple, trier les joueurs en ajoutant dans les seaux de leur équipe puis les Trier par leur numéro de maillot ou quelque chose comme trier les numéros de allant de 1-30 en 3 seaux de 1-10, 11-20, 21-30.

• le étape de combinaison est trivial (contrairement à la sorte de fusion). il suffit de copier les éléments de chaque seau dans le tableau original ou de joindre la tête de chaque seau avec la queue du seau précédent (dans le cas de listes liées)

• Radix/base pourrait être un type/instance du groupe/seau pendant le tri des numéros. Par conséquent, vous pourriez penser MSD radix comme un instance modifiée de la sorte de seau

• Bucket sort est pas en place mais stable algorithme de tri. Cependant, certaines variations de type seau pourrait ne pas être stable (si vous utilisez un algorithme de sous-tri qui n'est pas stable)