Les gens utilisent quicksort car c'est un tri en place avec une faible constante.
Heapsort est en place mais fait de gros déplacement dans la mémoire ce qui cause des problèmes dès qu'on veut trier de gros volumes de données.
Merge-sort n'est, par défault, pas en place. Il utilise deux fois plus de mémoire et ça pose des problèmes. On peut en faire un tri en place mais c'est beaucoup plus compliqué.
Dans la vraie vie, quicksort est effectivement plus rapide.
Dans un autre genre. L'algo de multiplication de polynômes qui a la meilleur complexité passe pas de la FFT et tourne en n.log(n). En pratique, à part pour des polynômes vraiment grands (plusieurs milliers de coefs), les gens utilisent l'algorithme de Kartsuba (en n^{3/2}) et des généralisations.
[^] # Re: sonntag
Posté par fmaz fmaz . En réponse à la dépêche Lisaac 0.12 en GPL v3. Évalué à 3.
Heapsort est en place mais fait de gros déplacement dans la mémoire ce qui cause des problèmes dès qu'on veut trier de gros volumes de données.
Merge-sort n'est, par défault, pas en place. Il utilise deux fois plus de mémoire et ça pose des problèmes. On peut en faire un tri en place mais c'est beaucoup plus compliqué.
Dans la vraie vie, quicksort est effectivement plus rapide.
Dans un autre genre. L'algo de multiplication de polynômes qui a la meilleur complexité passe pas de la FFT et tourne en n.log(n). En pratique, à part pour des polynômes vraiment grands (plusieurs milliers de coefs), les gens utilisent l'algorithme de Kartsuba (en n^{3/2}) et des généralisations.