Discussion :

[Grand sorcier]

Ca fait des années que je me casse le crane à trouver meilleur que quicksort() et puis ne n'y arrive pas.

Pourtant avant Hoare en 1960, les gens pensaient que le meilleur algo de tri etait le tri par insertion... Mais quand Hoare est arrivé il a pris tout le monde par surprise.

Pensez-vous qu'il existe mieux que quicksort ?

[2Eurocents]

Pensez-vous qu'il existe mieux que quicksort ?

En 1994, j'avais trouvé cet article sur le A-Sort (nom donné par son auteur), dans la revue Pascalissime.

Il me semble aussi avoir vu des tri en epi et des tri-fusion parfois plus rapide que quick-sort (bien que cela puisse peut-être dépendre de la distibution initiale.

Le "Tri casier" est aussi un bon candidat pour être plus rapide que quick-sort.

[Graffito]

Bonjour,

Il me semble qu'on peut trouver des algorithmes plus performants en cas de distribution "aléatoire". Toutefois dans les pire des cas qui ont évidemment une probabilité faible (loi des grands nombre), on pourra avoir des temps longs. Ces algorithmes ne garantissent donc pas une performance correcte dans tous les cas.

[Jedai]

Le quicksort n'est pas un si bon tri... Théoriquement il est moins bon que le tri fusion, entre autres parce qu'il ne garantit pas une complexité en O(n log n) mais peut dégénérer en O(n²) dans le pire des cas (lorsque le tableau est déjà trié et qu'on choisit le pivot au début ou à la fin par exemple...), tandis que le tri fusion est garantit en O(n log n) et n'approxime pas mal le meilleur des tris (qu'on peut trouver à la main mais qui est trop irrégulier pour être bien programmé efficacement).

Par ailleurs le tri par dénombrement ou par base sont bien meilleurs que le quicksort vu qu'ils sont en O(n) (dans certains cas), mais bien sûr ce ne sont pas des tris par comparaisons donc ils ne sont adaptés qu'à certains cas.

La prédominance du quicksort s'explique surtout par son caractère "en place" (dans un univers où la mémoire comptait beaucoup jusqu'il y a peu) et son adéquation avec la structure de tableau, extrèmement répandue dans les langages de programmation bas niveau. La situation est en train de changer parce que les langages de haut niveau sont en train de se répandre, et que la mémoire est un facteur beaucoup moins déterminant aujourd'hui.
Il faut voir aussi que les meilleurs algorithmes actuels sont en fait des mix employant des tris différent selon la longueur du tableau à trier, ils emploient souvent un dérivée du quicksort (ou du tri fusion) pour les gros tableaux mais choisisse le pivot de façon à éviter les cas dégénérés, ou coupe en plus que deux parts.

--
Jedaï

[Grand sorcier]

Moi j'aime bien le quicksort car il ne consomme quasiment pas de mémoire. Seulement ses performances oscillent entre O(nlogn) et 0(n^2).

De plus si j'ai une table qui prend plusieur Teraoctect et que je veux
faire un tri sur une telle table, je suis obligé de travailler sur une portion
de la table en mémoire. Mais la recursivité de quicksort parrait difficile
a mettre en oeuvre dans de telles circonstances.

Par contre la tactique "diviser pour regner" semble être très efficace. Au debut on prend une seule décision. L'itération d'après on prend 2 décisions. Puis 4, puis 8, etc....

En fait il me faudrait un algo en O(n log n) quelque la tableau en entrée avec une consommation de mémoire faible...

Mais en attendant je continue mes recherches fondamentales....

[Jean-Marc.Bourguet]

Si tu as plusieurs tera octets, les tris par fusion sont ce qui est classiquement utilise.

Cherche "external sort" pour les tris quand tout ne tient pas en memoire.

[Grand sorcier]

Le quicksort n'est pas un si bon tri... Théoriquement il est moins bon que le tri fusion, entre autres parce qu'il ne garantit pas une complexité en O(n log n) mais peut dégénérer en O(n²) dans le pire des cas (lorsque le tableau est déjà trié et qu'on choisit le pivot au début ou à la fin par exemple...), tandis que le tri fusion est garantit en O(n log n) et n'approxime pas mal le meilleur des tris (qu'on peut trouver à la main mais qui est trop irrégulier pour être bien programmé efficacement).

Par ailleurs le tri par dénombrement ou par base sont bien meilleurs que le quicksort vu qu'ils sont en O(n) (dans certains cas), mais bien sûr ce ne sont pas des tris par comparaisons donc ils ne sont adaptés qu'à certains cas.

La prédominance du quicksort s'explique surtout par son caractère "en place" (dans un univers où la mémoire comptait beaucoup jusqu'il y a peu) et son adéquation avec la structure de tableau, extrèmement répandue dans les langages de programmation bas niveau. La situation est en train de changer parce que les langages de haut niveau sont en train de se répandre, et que la mémoire est un facteur beaucoup moins déterminant aujourd'hui.
Il faut voir aussi que les meilleurs algorithmes actuels sont en fait des mix employant des tris différent selon la longueur du tableau à trier, ils emploient souvent un dérivée du quicksort (ou du tri fusion) pour les gros tableaux mais choisisse le pivot de façon à éviter les cas dégénérés, ou coupe en plus que deux parts.

--
Jedaï

Effectivement ! Je viens de lire un bouquin d'algo et le tri fusion est
garanti en O(nlog n) quelque soit la distribution du tableau.

Je vai donc me mettre à implementer cet algo. Le seul problème
est dans la fonction pour fusionner 2 tableaux triés. Il faudrait
pouvoir faire ça directement en place sur le tableau...

[PRomu@ld]

Le tri par tas est aussi en O(n log n)