push_swap est un projet d’algorithmique en C : trier une liste d’entiers en utilisant deux piles (A et B) et un set d’opérations strictement limité. Le challenge n’est pas seulement de “trier”, mais de produire une séquence de moves la plus courte possible.

⚠️ Le projet est actuellement en rework : je refactorise l’architecture et je compare plusieurs stratégies de tri pour améliorer la lisibilité et les performances (nombre d’opérations).

L’objectif est double :

• Concevoir une stratégie de tri adaptée à des opérations contraintes (push/swap/rotate).
• Mesurer l’impact de la complexité algorithmique et des choix d’implémentation sur le nombre de coups.

Principe

Le programme :

1. Parse les arguments (validation : entiers, doublons, overflow, etc.).
2. Représente les valeurs dans une pile A (pile B vide).
3. Applique une stratégie de tri via les opérations autorisées :

• sa/sb/ss (swap)
• pa/pb (push)
• ra/rb/rr (rotate)
• rra/rrb/rrr (reverse rotate)
  4. Affiche sur stdout la liste des opérations pour trier A.

Points importants

Stratégies testées

• Radix sort (binaire) :

• Je travaille sur une version indexée (compression des valeurs en rangs 0..n-1).

• Le tri se fait bit par bit : à chaque passe, on distribue dans B puis on remonte dans A.
• Complexité : ~O(n * log n) (plus précisément O(n * log M) où M est l’amplitude des valeurs, et en pratique M ≈ n après indexation).

• Très fiable : performance stable, peu sensible aux cas “pire”.

• Quicksort (expérimental) :

• Intéressant pour construire des partitions, mais plus délicat à optimiser en “moves”.

• Complexité : moyenne O(n log n), pire cas O(n²) si partitions déséquilibrées.

Ce qui compte vraiment

• Le score dépend du nombre d’opérations produites, pas uniquement de la complexité théorique.

• Les petits n (ex. 3/5/100/500) demandent souvent des heuristiques spécifiques :

• mini-tris dédiés pour 3 et 5

• stratégies chunk/pivots pour réduire les rotations

Contraintes respectées

• Langage : C
• Sortie : uniquement la liste des opérations
• Gestion stricte des erreurs : input invalide → Error (et exit)
• Zéro leak + gestion robuste des cas limites

Ce que ça m’a apporté

push_swap m’a appris à transformer un problème de tri classique en un problème d’optimisation sous contraintes : choisir une stratégie, raisonner sur la complexité, mais surtout analyser les mouvements réels (rotations/push) et refactoriser jusqu’à obtenir un code à la fois performant et maintenable.

Objectif

Trier une pile A (liste d’entiers) en utilisant une pile B et un set d’opérations limité. Le programme doit afficher sur stdout la liste des opérations nécessaires pour trier.

Contraintes d’entrée

• Uniquement des entiers valides
• Pas de doublons
• Gestion overflow / underflow
• En cas d’erreur : afficher Error et quitter

Opérations autorisées

• Swap : sa, sb, ss
• Push : pa, pb
• Rotate : ra, rb, rr
• Reverse rotate : rra, rrb, rrr

Ce qui est évalué

• La pile A doit finir triée
• Le score dépend du nombre de coups (moins = mieux)

1) Pré-traitement : indexation (compression)

Pour stabiliser les performances, j’utilise une compression des valeurs : chaque nombre est remplacé par son rang dans l’ordre trié (0..n-1).

Avantages :

• simplifie le tri binaire
• borne l’amplitude : M ≈ n

2) Radix sort (binaire)

Principe : trier bit par bit.

• À chaque passe k (bit k) :

• si le bit vaut 0 → push vers B

• sinon → rotate A
• Puis on remonte tout de B vers A.

Complexité (théorie) : O(n * log M)

• après indexation : M ≈ n → O(n log n)

Pourquoi c’est efficace ici :

• performances stables (pas de “pire cas” brutal)
• très bon baseline pour n = 100/500

3) Quicksort (expérimental)

Approche basée sur des partitions (pivots/chunks), intéressante mais plus difficile à optimiser en nombre d’opérations.

Complexité :

• moyenne : O(n log n)
• pire cas : O(n²) si partitions déséquilibrées

Note importante

La complexité ne fait pas tout : dans push_swap, le vrai coût est le nombre de moves. Une stratégie théoriquement bonne peut être moins performante si elle provoque trop de rotations/push.

push_swap — Rework & Roadma

Objectif du rework : transformer push_swap en un laboratoire d’algorithmes capable de tester plusieurs solveurs, comparer leurs scores, puis afficher automatiquement la meilleure solution pour l’entrée donnée.

Pourquoi ce rework

J’ai une version fonctionnelle (radix) qui trie correctement, mais je veux aller plus loin que “ça marche” :

• Comparer des stratégies : vérifier si un algorithme est réellement dominant sur push_swap, ou si certaines approches gagnent sur des cas précis.
• Objectiver la perf : mesurer le score (nombre d’opérations) et comprendre pourquoi ça gagne/perd.
• Créer une base propre : architecture modulaire, testable, qui permet d’ajouter un nouvel algo sans réécrire tout le projet.

Vision

Le programme devient un orchestrateur :

1. Parse & valide l’input.
2. Lance plusieurs solveurs (algorithmes).
3. Simule leurs opérations (sans print), vérifie que le tri est valide.
4. Compare les scores.
5. N’affiche que la meilleure séquence (comme attendu par l’éval 42).

Algorithmes visés

Baselines

• Radix binaire (avec indexation 0..n-1) : stable et très fiable.
• Mini-solvers pour n ≤ 5 : séquences courtes, quasi optimales.

Approches score-oriented

• Chunk / pivots + réinsertion cost-based : réduire les rotations inutiles.
• Hybrides Quick + Insertion : partition rapide puis finition locale.
• Hybrides Merge + Insertion (esprit Timsort) : runs/merges + insertion sur petits segments.

Axe “chaos / research”

Objectif : explorer des approches qui peuvent parfois surprendre sur certains patterns.

• Chaotic pivots / chunk sizes : utiliser des paramètres générés par une carte chaotique (ex. logistic map) et observer des zones stables/instables.
• Recuit simulé (Simulated Annealing) : partir d’une solution stable (radix/chunks) puis améliorer via mutations contrôlées.

Ces modes seront derrière un flag --research : plus lents / non déterministes, mais parfaits pour explorer des “courbes étranges”.

Architecture cible

• core/sim : simulateur A/B + primitives + compteur d’opérations
• ops/recorder : enregistrement de la séquence (vector), export final
• solvers/* : un fichier par algo, interface commune solve_*()
• compare/ : runner multi-algo + policy de sélection
• tests/ (local) : générateurs, scénarios, stats

Roadmap

Phase 1 — Base solide

• [ ] parsing + validation (doublons, overflow, erreurs cohérentes)
• [ ] indexation (compression) stable
• [ ] simulateur + recorder d’ops (source de vérité)

Phase 2 — Solveurs “must-have”

• [ ] mini-solvers (2/3/5)
• [ ] radix final (baseline propre)

Phase 3 — Score & heuristiques

• [ ] chunk/pivots + réinsertion cost-based
• [ ] hybride quick + insertion
• [ ] mode --compare (debug) : tableau algo → ops → valid → temps (optionnel)

Phase 4 — Recherche / chaos

• [ ] chaotic pivots (param → score)
• [ ] simulated annealing (amélioration locale)
• [ ] génération de lots + stats (moyenne, médiane, p95, taux de victoire)

Phase 5 — Qualité & packaging

• [ ] tests automatiques + cas limites
• [ ] vérif leaks
• [ ] README “projet + choix techniques + comment comparer”

Ce que je vise

Un push_swap qui :

• reste lisible et maintenable,
• sort une solution compétitive (radix/chunks),
• et permet d’explorer/visualiser quand et pourquoi un algo devient meilleur qu’un autre.