Discussion :

[yo_haha]

Bonjour,
Je voudrais savoir quelle est la meilleure méthode de tri?
Est-ce qu'il y a une seule méthode optimale ou bien ça dépend de chaque problème?
En somme, comment reconnaître la méthode qu'il faut utiliser?

Cordialement,
yo_haha

[kromartien]

Je crois que il est prouvé mathématiquement que la meilleure efficacité atteignable pour un tri sur une liste de n nombre est en O(nlog(n)). Donc si tu as un tri qui a cette efficacité, c'est probablement le meilleur que tu puisses trouver.

Maintenant, je pense qu'il peut y avoir des différences subtiles entre les différentes méthodes de tri qui sont en nlog(n) qui font qu'on pourra en préférer l'une à l'autre en fonction du contexte d'utilisation.

[phryte]

Bonjour.

tri qui sont en nlog(n)

Smoothsort est dans ce cas.
http://fr.wikipedia.org/wiki/M%C3%A9thode_de_tri

[ToTo13]

Bonjour,

oulala... attention aux conditions !

Pour connaître l'efficacité d'un tri, il faut regarder sa complexité (qui se calcule dans le pire des cas).
MAIS, il y a deux types de tri :
- 1 - les tris par comparaisons, pour lesquels on a aucune information sur les chiffres qui sont contenu dans le tableau.
- 2 - et les tris pour lesquels on connaît par exemple le plus petit et le plus grand chiffre.


1 - Pour les tris par comparaison, les plus rapides sont en O(n log(n)) comme le tris par tas. Mais le tri le plus rapide en général est le QuickSort (ou tri rapide) aussi en O(n log(n)), mais avec une constante plus faible que le tri par tas. Le seul défaut de ce tri, c'est que dans le pire des cas, il est en O(n^2) (mais des améliorations existent). La probabilité que le pire des cas se produise est quasiment nulle, mais sait on jamais.
Donc si tu dois être sûr que ton algo tri en O(n log(n)) (et que le pire des cas engendrerai une catastrophe pour ton soft), tu prends le tris par tas (c'est celui utilisé dans de nombreux calculateurs). Mais en règle générale, le Quicksort est plus rapide. Tu n'as qu'à faire le test pour te le prouver.

2 - Si tu connais le plus grand et le plus petit chiffre de ton tableau, il te suffit alors de faire un tri par dénombrement qui a une complexité en O(n) (pour être exacte, c'est en O(2n), mais on écrit pas les constantes).