C'set un peu l'esprit du hash-sorting qui est lui aussi en O(n) : tu as une table de hash où tu balances toutes les valeurs à trier et à la fin tu la parcourt dans l'ordre pour recréer le tableau trié (si j'ai mal expliqué cf google ça doit y être).
Et si on veut un tri basé sur des comparaisons on a les tris qui s'occupent d'abord des bits de poids fort puis des bits de poids faibles de ton entier, ça donne des complexités comme O(n*log(log(n))), ça doit aussi se trouver sur google.
En fait, le tri O(n*log(n)) est optimal avec quelques hypothèses :
- tu fais le tri in-situ
- tu as une fonction de comparaison dont tu ne connais pas les propriétés à priori
- tu as juste le droit de modifier ton tableau avec une fonction inverse(a,b) qui... inverse a et b.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Stephane Marchesin . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 9.
Et si on veut un tri basé sur des comparaisons on a les tris qui s'occupent d'abord des bits de poids fort puis des bits de poids faibles de ton entier, ça donne des complexités comme O(n*log(log(n))), ça doit aussi se trouver sur google.
En fait, le tri O(n*log(n)) est optimal avec quelques hypothèses :
- tu fais le tri in-situ
- tu as une fonction de comparaison dont tu ne connais pas les propriétés à priori
- tu as juste le droit de modifier ton tableau avec une fonction inverse(a,b) qui... inverse a et b.