Tri

Mais pas toujours ^^

Bah si ma mémoire est bonne, le quicksort peut être en O(n²) par exemple si on tri un tableau déjà trié.
Après il y a des moyens de contourner ce problème en "mélangeant" les données avant de les trier.
Ou bien s'orienter vers des tris comme heapsort ou smoothsort qui sont toujours en O(n.log n)

oui c'est vrai, le quicksort peut parfois être très médiocre, mais on accorde l'effort en fonction du problème, et s'il s'agit de trier un tableau d'une centaine d'entrées une seule fois...

Pour trier une centaine d'entrée une fois, tu fais un bubblesort ^^
Pour trier des millions d'entrées, tu fais du calcul parallèle sur un réseau papillon
Et entre les deux y a le choix ;-)

Je pense que si quicksort est le plus utilisé dans les implémentations c'est parce qu'il est peu gourmand en ressource, contrairement au tri par fusion par exemple qui utilise deux fois la mémoire initiale du tableau pour faire le calcul.

D'ailleurs dans le lien de JooS, les statistiques sont en nombre d'écritures+comparaisons, habituellement quand on parle de complexité, on évalue théoriquement le nombre de comparaisons pour le pire des cas, et les résultats seraient légèrement différents. D'ailleurs ici on ne sait pas trop dans ces stats comment sont les tableaux avant le tri (triés, presque triés, triés à l'envers...) certains tris sont meilleurs si on est dans un certain type de configuration, et il faut savoir profiter de ces avantages.

Tout à fait d'accord^^. Dès qu'on souhaite trier de grosse quantitées en critères multiples, il est nécessaire d'exploiter plusieurs approches. En tant qu'amateur d'optimisation poussée, j'ai longuement muri ce sujet, et ce que j'ai trouvé de plus efficace ce fait en deux points :

- Evaluation d'une valeur grossière 16 bits compactée pour chaque entrée, pouvant être déterminée selon plusieurs clés, mais pas forcément toutes, tout en comptant le nombre d'entrées pour chaque valeur grossières,
Repositionnement direct des entrées en fonction de chaque valeur approchée. A ce stade on trouve de gros blocs d'entrées correctement positionnés, mais anarchiques en leur sein.

- Si le nombre d'entrées reste important, on recommence en approfondissant les critères de clés, sinon utilisation d'un quicksort modifié, positionnant les valeurs supérieures, inférieures ET égales au pivot de comparaison.
L'étape 'Quicksort' se fait de manière 'fenêtrée', le tri étant effectué jusqu'au bout uniquement là où le besoin est réel - la zone affichée par exemple-, grâce à un tableau de flags, déterminant les zones dans lesquelles le tri à été finalisé.

J'ai développée une unitée de 2500 lignes en assembleur à ce sujet, en testant différentes possibilitées, et celle-çi a donné les meilleurs résultats. J'obtiens un tri de 250000 fichiers (nom, taille, ext, etc...) en 80 ms en moyenne sur athlon 3500.

Après, pour un débutant qui souhaite juste réussir à trier un petit tableau, un quicksort peut convenir !

Les algorithmes sont toujours les mêmes, peu importe le langage...
Même pour trier nos chaussettes (ou autre ^^) on pourrait dire quel algo est le mieux :p

Tout à fait !