Hassan Ed-dybNotesEN

push_swap

Trier, en un minimum de coups.

push_swap — Trier, en un minimum de coups.

Trier des entiers avec deux piles et un jeu d'instructions limité, en un minimum d'opérations.

Le problème

Trier est facile, jusqu'à ce que les seuls coups permis soient swap, push et rotate sur deux piles, et que chaque coup compte.

Comment je l'ai construit

  1. 01Implémente les 11 opérations (sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr) sur deux piles.
  2. 02Une stratégie optimisée qui limite le nombre d'instructions, même pour de grandes entrées.
  3. 03Valide les entrées : pas de doublons, pas de dépassement, pas de valeurs non numériques.

Ce que j'en retiens

  • — La complexité algorithmique mesurée en opérations réelles, pas seulement en théorie.
  • — Optimiser face à un benchmark.

push_swap a été réalisé dans le cadre du cursus d'ingénierie logicielle de 1337 Coding School (42 Network, UM6P), où chaque projet est construit de zéro et évalué par des pairs.