Un tri en O(n), je doute
Si, si, ça existe, c'est pas un algo de tri général, mais en faisant des suppositions sur les données, ça existe. Par exemple, si on suppose qu'il existe un nombre fini (petit) de valeurs possibles, alors tu peux créer un tableau avec une case par valeur et dans chaque case tu mets une liste chainée pour mettre les valeurs.
Donc l'algo est le suivant :
1 - Pour chaque donnée, la placer à l'avant de la liste chainée dans la case qui lui correspond
2 - Parcourir le tableau pour mettre bout à bout chaque liste chainée (on suppose que ce sont des listes simplement chainées donc il faut reparcourir tous les éléments.
Au final, on a parcouru deux fois la liste des éléments. On a donc bien un algo en O(n).
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par harbort . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 7.