Bonsoir a tous !
Quelqu’un connaîtrais un algorithme permettant de trier une pile de donnée (LIFO) avec une complexité meilleure qu'une complexité quadratique (O(n^2)).

Une solution assez bourrine est de convertir ta pile en tableau
(et ce n'est pas la pire des méthodes en plus )

Le tri fusion peut s'y prêter, et je pense, le trie le plus simple à coder dans ce cas.

Bah en fait si tu convertis en tableau, ça te prend O(n) et ensuite trier un tableau ca se fait en O(n log(n)) qui est optimale pour un tri (sauf cas particulier). Donc c'est optimale au sens des O pour le temps de calcul, mais pas en mémoire et clairement tu peux faire mieux en procédant directement au tri quand tu fais sortir de la pile via un arbre comme on le fait pour les tableaux en fait.