Pourquoi Radix Sort ?

Dans le tri radix, nous trions d'abord par chiffre le moins significatif puis nous trions par deuxième chiffre le moins significatif et ainsi de suite et nous nous retrouvons avec une liste triée.

Maintenant, si nous avons une liste de nombres, nous avons besoin de bits pour distinguer ces nombres. Le nombre de passes de tri radix que nous effectuerons sera donc . Chaque passage prend temps et donc le temps d'exécution du tri radix estlog n log n O ( n ) O ( n log n $n$$\log n$$\log n$$O(n)$$O(n \log n)$

Mais il est bien connu qu'il s'agit d'un algorithme de temps linéaire. Pourquoi?

si nous avons une liste de nombres dont nous avons besoin bitslog $n$$\log n$

Non: si nous avons une liste de nombres entre et , nous avons besoin de bits. Il n'y a aucune relation entre et en général.2 k - 1 k k log $0$$2^k - 1$$k$$k$$\log n$

Si les nombres sont tous distincts, alors , et le tri radix sur des nombres distincts a donc une complexité temporelle de . En général, la complexité du tri radix est où est le nombre d'éléments à trier et est le nombre de bits dans chaque élément.Ω ( n log n ) Θ ( $\log n \ge k$$\Omega(n \log n)$n $\Theta(n \, k)$$n$$k$

Dire que la complexité du tri radix est signifie prendre une taille de bit fixe pour les nombres. Cela implique que pour suffisamment grand , il y aura de nombreuses valeurs en double.$O(n)$$n$

Il existe un théorème général selon lequel une méthode de tri de tableau ou de liste qui fonctionne en comparant deux éléments à la fois ne peut pas s'exécuter plus rapidement que dans le pire des cas. Le tri Radix ne fonctionne pas en comparant les éléments, mais la même méthode de preuve fonctionne. Le tri Radix est un processus de décision pour déterminer la permutation à appliquer au tableau; il y en apermutations du tableau, et le tri radix prend des décisions binaires, c'est-à-dire qu'il décide d'échanger ou non deux éléments à chaque étape. Après décisions binaires, le tri radix peut décider entre permutations. Pour atteindre lepermutations possibles, il faut que .n ! m 2 m n ! m ≥ log ( n ! ) = Θ ( n log n $\Theta(n \log n)$$n!$$m$$2^m$$n!$$m \ge \log (n!) = \Theta(n \log n)$

Une hypothèse dans la preuve que je n'ai pas écrite ci-dessus est que l'algorithme doit fonctionner dans le cas où les éléments sont distincts. Si l'on sait a priori que les éléments ne sont pas tous distincts, alors le nombre de permutations potentielles est inférieur au complet. Lors du tri des nombres à bits, il n'est possible d'avoir éléments distincts que lorsque ; dans ce cas, la complexité du tri radix est en effet . Pour des valeurs plus grandes de , il doit y avoir des collisions, ce qui explique comment le tri radix peut avoir une complexité inférieure à lorsque .k n n ≤ 2 k Ω ( n log n ) n Θ ( n log n ) n > 2 $n!$$k$$n$$n \le 2^k$$\Omega(n \log n)$$n$$\Theta(n \log n)$$n \gt 2^k$

Soyez prudent avec votre analyse: que supposez-vous pour faire fonctionner le tri en temps ? En effet, chacun de vos chiffres est compris entre et , ce qui signifie que vos chiffres peuvent prendre valeurs possibles. Vous avez besoin d'un algorithme de tri stable, vous pouvez par exemple choisir le tri par comptage. Le comptage du tri s'exécute en temps . Si , le tri de comptage s'exécute en temps linéaire.0 k - 1 k Θ ( n + k ) k = O ( n $O(n)$$0$$k-1$$k$$\Theta(n+k)$$k=O(n)$

Chacune de vos chaînes ou nombres a des chiffres en . Comme vous le dites, vous faites passer sur eux. Par conséquent, le tri radix s'exécute clairement en temps . Mais si nous considérons constant et , nous voyons que le tri radix s'exécute en temps linéaire.d Θ ( d ( n + k ) ) d k = O ( n $d$$d$$\Theta(d(n+k))$$d$$k=O(n)$

Je pense que l'hypothèse est fausse. Vous pouvez effectuer un tri radix avec des nombres en hexadécimal, par exemple. Ainsi, à chaque étape, vous divisez votre tableau de nombres en compartiments.$k = \log_2(n)$$16$