Tri Radix: versions LSD et MSD
Le livre "Introduction aux Algorithmes" mentions à propos de la version LSD (le moins significatif) de radix sort. Toutefois, comme d'autres l'ont souligné ici dans stackoverflow, il existe également une version MSD (le chiffre le plus significatif). Je veux donc connaître le pour et le contre de chacun d'entre eux. À mon avis, la version LSD a certains avantages par rapport à la version MSD, mais je ne suis pas sûr. D'où la question.
3 réponses
Prise à partir du lien, pourrait être utile: http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx (tout En bas)
le plus gros problème avec le LSD radix sort est qu'il commence par les chiffres qui font la moindre différence. Si nous pouvions commencer avec les chiffres les plus significatifs, le premier passage serait un long chemin vers le tri de la gamme entière, et chaque passage après cela serait tout simplement gérer les détails. L'idée du tri MSD radix est de diviser tous les chiffres, avec une valeur égale à leur propre seau, puis faire la même chose avec tous les seaux jusqu'à ce que le tableau est trié. Naturellement, cela suggère un algorithme récursif, mais cela signifie aussi que nous pouvons maintenant trier les éléments de longueur variable et nous n'avons pas à toucher tous les chiffres pour obtenir un tableau trié. Cela rend MSD radix trier considérablement plus rapide et plus utile.
LSD est plus rapide que MSD quand il y a une longueur fixe. MSD est trop lent pour les petits fichiers, et il besoin d'un grand nombre d'appels récursifs sur les petits fichiers.
Comme dans le livre Algorithmes, LSD et MSD sont tous deux des algorithmes de tri de tableaux de chaînes de caractères, basés sur ce qu'on appelle le comptage indexé de clés plutôt que sur des comparaisons. Par conséquent, LSD et MSD ont une durée de fonctionnement différente par rapport au tri rapide ou au tri de fusion traditionnel.
comme L'a mentionné Dzhabarov, la plus grande différence entre le LSD et le MSD est que le MSD considère d'abord le chiffre ou le caractère le plus significatif, qui par nature trie les chaînes sans itérer à travers tous les les chiffres dans les cordes. C'est un avantage. Cependant, une mise en œuvre récursive du MSD utilise plus d'espace que le LSD.
le tableau ci-dessous illustre certaines parties de la différence entre le tri rapide, le LSD et le MSD.
algorithm running time extra space
quicksort N(lgN)^2 1
LSD NW N
MSD between N and NW N + WR
où N est la longueur du tableau, et W est la longueur de la chaîne, et R est la taille de radix.
PS: comme mentionné dans le livre, le système de tri Java utilise un algorithme de tri général avec une comparaison rapide des chaînes de caractères et non LSD ou MSD.