PROJECT DOSSIER // [PUSH SWAP]VOIR LA SOURCERETOUR AUX PROJETS →

01 // LE PROJET EN BREF

PUSH SWAP

C

Trier une liste avec seulement deux piles et une poignée d'opérations autorisées.

Le problème est de trier des nombres, mais avec des règles très restrictives : on ne dispose que de deux piles et de quelques mouvements élémentaires, un peu comme un jeu de patience. L'objectif n'est pas seulement d'y arriver, mais d'y arriver en un minimum de coups — ce qui transforme un exercice de tri en un vrai problème d'optimisation.

Binaire push_swap triant une liste d'entiers via deux piles et un jeu d'opérations restreint, à l'aide d'un tri radix décimal qui écrit les instructions au fil de l'eau.

PRINCIPALC
RÉALISATIONPROJET D’ÉQUIPE
VÉRIFICATIONmake
SOURCEINSPECTOR READY
PIÈCES JOINTES (Images, Photos, Videos)

02 // REPÈRES DU PROJET

DATE:
2018
LANGAGE PRINCIPAL:
C
NOTE:
A
DURÉE:
2 semaines
SECONDARY:
—
STACK:
Makefile / gcc

03 // APPORTS CLÉS

  • Un tri radix adapté à un jeu d'opérations qui n'autorise ni accès direct ni comparaison arbitraire
  • Deux listes doublement chaînées circulaires pour rendre rotation et transfert en temps constant
  • Instructions écrites au fil de l'eau, sans liste intermédiaire en mémoire

AU-DELÀ DU SUJET

  • Tri radix (radix.c) sur la représentation binaire des valeurs, au lieu d'un tri par insertion naïf
  • Tri à bulles réduit conservé pour les très petites listes, où le radix n'est pas rentable

04 // ARBORESCENCE DU CODE

LECTURE DES SOURCES…