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

Seau de tri et tri radix sont des cousins proches; seau de tri va de MSD pour le LSD, alors que radix tri peut aller dans les deux "directions" (LSD ou TMS). Comment faire les deux algorithmes de travail, et en particulier en quoi diffèrent-elles?

InformationsquelleAutor Lazarus | 2010-12-16
  1. 42

    Le passage initial de deux RadixSort et BucketSort est exactement le même. Les éléments sont mis en buckets (ou bins) de l'accroissement de la portée (par exemple de 0 à 10, 11 à 20, ... 90-100), selon le nombre de chiffres dans le plus grand nombre.

    Dans le passage suivant, cependant, BucketSort commandes jusqu'ces "seaux" et ajoute-les dans un tableau. Cependant, RadixSort ajoute les seaux sans plus de tri et de "ré-seaux" il basé sur le deuxième chiffre (des dizaines) de nombres. Par conséquent, BucketSort est plus efficace pour les Denses tableaux, alors que RadixSort peut gérer clairsemée (enfin, pas exactement rares, mais espacé) des tableaux bien.

    • Pourriez-vous développer cette réponse pour expliquer pourquoi la complexité de ces deux méthodes sont différentes? c'est à dire pourquoi est-seau de tri en O(n+k), mais radix de tri en O(nk)?
    • C'est une vieille question, mais si quelqu'un a la lecture de ce veut savoir. Il ressort de la description, seau tri-t-on passer sur N, puis fusionne K seaux (de l'ordre à l'intérieur du seau est arbitraire). Alors que radix de tri ne passer un pour chaque compartiment, ici, je pense que le tri des chaînes serait meilleur exemple, de sorte que vous ne K passe de la complexité N.
    • Qu'entendez-vous par "BucketSort commandes jusqu'ces "compartiments"? Chaque seau triés avec un algorithme différent ou quoi? Parce que chaque seau n'est pas entièrement triée si vous groupe par 10s.
    • "Par conséquent, BucketSort est plus efficace pour les Denses tableaux, alors que RadixSort peut manipuler des matrices creuses bien." - pourquoi est-ce le cas?
    InformationsquelleAutor Akash
  2. 22

    Seau de Tri et Tri Radix sont comme sœur algorithmes de tri parce qu'ils ne sont pas de comparaison sortes et l'idée générale est la même. Aussi, ils sont un peu abstrait dans la mise en œuvre.

    Tri Radix:

    • Radix signifie base(binaire, octal, décimal,etc). Par conséquent, ce tri est pour les nombres (également utilisée pour les chaînes). Cela fonctionne lorsque chaque élément de E est ek...e2e1e0, où ei est dans une certaine gamme. (généralement 0 à une base comme 0 à 9 en décimal ou de 0 à 255 en caractères ASCII)

    • Il utilise ensuite k passe de stabilité d'un sous-algorithme de tri (Il doit être stable ou d'autre Radix de tri ne fonctionne pas) à trier les nombres. Ce sous-algorithme de tri est généralement de Comptage, de tri ou un Seau de tri mais il ne peut pas être Radix trier lui-même.

    • Vous pouvez commencer à partir de Chiffres Plus Importantes ou du Chiffre le Moins Significatif, car il mélange tout nombre à chaque passage (de k à 0 ou de 0 à k)

    • C'est un stable algorithme de tri.

    Seau Tri:

    • Il sépare le tableau en les petits groupes ou les seaux et les trie individuellement à l'aide d'un sous-algorithme de tri ou de l'appel récursif à lui-même et puis combine le résultat. Par exemple, trier les joueurs par l'ajout dans les seaux de leur équipe, puis de les trier par leurs nombres de jersey ou de quelque chose comme le tri des nombres allant de 1 à 30 en 3 seaux de 1 à 10, 11 à 20, 21 à 30.

    • La combiner étape est trivial (contrairement à la fusion et le tri). il suffit de copier les éléments de chaque compartiment arrière dans le tableau d'origine ou de rejoindre la tête de chaque seau avec de la queue de la précédente seau (dans le cas de listes chaînées)

    • Radix/base pourrait être un type/instance du groupe/seau alors que le tri des nombres. Par conséquent, vous pourriez penser MSD radix comme une modification de l'instance de seau de tri

    • Seau tri est pas place mais stable algorithme de tri. Toutefois, des variations de seau de tri peut ne pas être stable (si vous utilisez un sous-algorithme de tri qui n'est pas stable)

    InformationsquelleAutor dev_ankit