Quelqu'un pour infirmer/confirmer/completer/me faire interner?
Si tu utilises une table de hachage, tu peux effectivement trier en o(n). Mais bon, ca implique d'avoir une bonne clef de hachage et de créer une structure annexe (la table de hachage) au moins aussi grande que le tableau à trier. Après, pour trier, c'est simple : dans une première passe tu insères tous les éléments dans la table de hash, et dans une deuxième passe tu parcours la table pour relire les éléments dans l'ordre (pour cette deuxième étape, il faut avoir pensé à utiliser une fonction de hachage qui permette de déduire l'index de l'élément suivant à partir de l'élément courant).
Bref tu crées une structure en mémoire plus grande que ton tableau (pour éviter trop de collisions dans ta table de hachage) ce qui utilise plus du double de mémoire dans le cas qui nous intéresse le plus si on cherche un algo de tri en o(n) : pour n très grand !
Voila, ca demande effectivement de bonnes connaissance à priori sur les données à trier (pour faire une bonne clef de hachage).
[^] # Re: Soft de peer to perr
Posté par Stephane Marchesin . En réponse au journal Soft de peer to perr. Évalué à 1.
Si tu utilises une table de hachage, tu peux effectivement trier en o(n). Mais bon, ca implique d'avoir une bonne clef de hachage et de créer une structure annexe (la table de hachage) au moins aussi grande que le tableau à trier. Après, pour trier, c'est simple : dans une première passe tu insères tous les éléments dans la table de hash, et dans une deuxième passe tu parcours la table pour relire les éléments dans l'ordre (pour cette deuxième étape, il faut avoir pensé à utiliser une fonction de hachage qui permette de déduire l'index de l'élément suivant à partir de l'élément courant).
Bref tu crées une structure en mémoire plus grande que ton tableau (pour éviter trop de collisions dans ta table de hachage) ce qui utilise plus du double de mémoire dans le cas qui nous intéresse le plus si on cherche un algo de tri en o(n) : pour n très grand !
Voila, ca demande effectivement de bonnes connaissance à priori sur les données à trier (pour faire une bonne clef de hachage).