/* ************************************************************************** */ /* */ /* ::: :::::::: */ /* push_swap.c :+: :+: :+: */ /* +:+ +:+ +:+ */ /* By: lkantzer <lkantzer@student.42.fr> +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/01/10 14:27:36 by lkantzer #+# #+# */ /* Updated: 2025/04/12 14:21:26 by lkantzer ### ########.fr */ /* */ /* ************************************************************************** */
push_swap
Trier avec un jeu d'instructions volontairement pauvre
Trier une pile avec onze opérations autorisées, en minimisant leur nombre. L'exercice est de concevoir le tri, pas de l'écrire.
- 11
- instructions
- 2
- piles
- nombre de coups
- critère
Les onze opérations
Deux piles, A et B. Tout commence en désordre dans A, tout doit finir trié dans A avec B vide. On ne lit jamais ailleurs qu'au sommet, et on n'échange jamais deux éléments quelconques : il n'y a que ces onze mots, écrits un par ligne sur la sortie.
- sa · sb · ss
- Échanger les deux premiers de A, de B, ou des deux à la fois.
- pa · pb
- Prendre le premier d'une pile et le poser en tête de l'autre. Sans effet si la pile de départ est vide.
- ra · rb · rr
- Décaler la pile vers le haut : le premier élément devient le dernier.
- rra · rrb · rrr
- L'inverse : le dernier élément remonte en tête.
Les trois formes doubles — ss, rr, rrr — ne sont pas du sucre syntaxique : elles font le travail de deux opérations pour le prix d'une, et c'est là que le score se gagne.
L'algorithme
Les valeurs sont d'abord remplacées par leur rang : on ne trie plus des nombres quelconques mais 0, 1, 2… n−1. À partir de là, on sait toujours où chaque élément doit finir.
- 01Découper
Les rangs sont vus par tranches, et non un par un. La largeur d'une tranche vaut environ un cinquième de la pile.n / 5
- 02Vider A
On fait tourner A et on pousse en B tout ce qui appartient à la tranche courante. Les plus petits de la tranche reçoivent un rb de plus, qui les enfonce au fond de B — la remontée les y retrouvera dans le bon ordre.
- 03Remonter
B se vide à l'envers : à chaque tour on cherche le plus grand rang restant, on le ramène en tête par le côté le moins cher — rb s'il est dans la moitié haute, rrb sinon — puis pa.
- 04Le score
Rien ne mesure le temps d'exécution : c'est le nombre de lignes écrites qui fait la note. Un tri correct mais bavard est un tri raté.
La largeur des tranches est le seul vrai réglage : trop large, A tourne dans le vide en cherchant des éléments rares ; trop étroite, on repasse trop souvent sur toute la pile.
Pile A — 40
Pile B — 0
40 valeurs, onze opérations autorisées. La pile A est en noir, la pile B en terracotta ; chaque trait est une valeur, sa longueur son rang. La séquence entière est calculée d'abord, puis rejouée — c'est le nombre d'opérations produites qui fait la note du projet.
- 01Deux piles, onze instructions, aucun accès aléatoire
- 02La note dépend du nombre d'opérations produites
- 03Stratégie par blocs, nettement plus économe que l'approche naïve
- 04Les itérations successives sont conservées dans le dépôt
Compter les coups, pas les lignes
Optimiser veut dire choisir, pour chaque élément, le chemin de rotation le moins cher — y compris les rotations combinées qui font tourner les deux piles à la fois.