La bonne solution est plutôt de s'assurer que l'algo de tri ne peut facilement dégénérer, sans être d'emblée non plus en O(n**2)
Voir introsort pour ceux que ça intéresse. Au passage, de nombreux environnements d’exécution utilisent « quicksort » pour trier, sans plus de précision dans leur doc (je n’ai pas regardé le code source). Si ce n’est pas une version de quicksort intégrant une astuce pour éviter le cas pathologique, ça peut donner des idées pour la prochaine fois...
[^] # Re: N'optimiser que si nécessaire
Posté par ɹǝıʌıʃO . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 1.
Voir introsort pour ceux que ça intéresse. Au passage, de nombreux environnements d’exécution utilisent « quicksort » pour trier, sans plus de précision dans leur doc (je n’ai pas regardé le code source). Si ce n’est pas une version de quicksort intégrant une astuce pour éviter le cas pathologique, ça peut donner des idées pour la prochaine fois...