École 42
Push_swap
Trier une pile d'entiers en un minimum de mouvements, avec seulement deux piles et un jeu d'instructions restreint.
Le contexte
Push_swap prend une liste d'entiers en argument et doit produire la suite d'instructions (sa, pb, ra, rra, etc.) qui trie la pile, en minimisant leur nombre. Le tri s'appuie sur un découpage par index façon tri par base pour les grandes piles, et une gestion dédiée pour les cas à deux, trois ou cinq éléments.
Un algorithme déjà solide
Contrairement à d'autres projets de ce dépôt, l'algorithme de tri lui-même n'a pas eu besoin d'être reconstruit : vérifié sur des piles de 3, 5, 100 et 500 éléments avec un simulateur qui rejoue les instructions produites, il trie correctement à chaque fois, avec un nombre de mouvements dans une fourchette raisonnable (1084 pour 100 éléments, 6784 pour 500).
Distribuer plutôt que comparer
Trier avec seulement deux piles et un jeu d'instructions restreint pousse à sortir des algorithmes de tri comparatifs classiques : la stratégie retenue découpe les grandes piles en tranches par index, dans l'esprit d'un tri par base, plutôt que de comparer les éléments deux à deux. Comprendre pourquoi cette approche réduit le nombre de mouvements sur de grandes piles, et pourquoi elle devient inutile en dessous d'un certain seuil où une gestion dédiée à 2, 3 ou 5 éléments est plus efficace, a été le vrai apprentissage du projet : le bon algorithme dépend autant de la contrainte, ici le coût d'un mouvement, que de la taille du problème.
Mesurer la qualité d'un tri
Un simulateur qui rejoue les instructions produites permet de vérifier à la fois la correction du tri et son coût réel : sur des piles de 100 et 500 éléments, cela donne respectivement 1084 et 6784 mouvements, une façon concrète de comparer des variantes d'algorithme entre elles plutôt que de s'en tenir à une complexité théorique.
Code bientôt disponible sur GitHub.