🔄 Push Swap

Un projet de tri efficace utilisant deux piles et un ensemble limité d'opérations.

📋 Table des matières

• Description
• Algorithme
• Installation
• Utilisation
• Règles
• Checker
• Visualiseur
• Exemples

📖 Description

Push Swap est un projet de l'école 42 qui consiste à trier une pile de nombres entiers en utilisant un minimum d'opérations. Le programme doit utiliser deux piles (A et B) et un ensemble restreint d'opérations pour effectuer le tri.

Objectifs

• Trier une pile de nombres dans l'ordre croissant
• Minimiser le nombre d'opérations nécessaires
• Optimiser l'algorithme pour différentes tailles de piles

🧮 Algorithme

Le programme utilise un algorithme optimisé qui s'adapte à la taille de la pile :

• Petites piles (≤ 3 éléments) : Tri direct avec comparaisons
• Piles moyennes (4-5 éléments) : Tri par insertion optimisé
• Grandes piles (> 5 éléments) : Algorithme de tri par chunks avec calcul de coûts

L'algorithme calcule le coût de chaque mouvement possible et choisit toujours l'opération la plus efficace.

🔧 Installation

Prérequis

Pour compiler le projet complet (incluant le visualiseur), vous aurez besoin de :

# Mise à jour du système
sudo apt-get update

# Outils de compilation
sudo apt-get install cmake g++ clang

# Bibliothèques pour le visualiseur
sudo apt-get install libgl1-mesa-dev libglu1-mesa-dev
sudo apt-get install libx11-dev libxrandr-dev
sudo apt-get install libudev-dev libfreetype-dev

Compilation

# Cloner le repository
git clone https://github.com/Nass26dev/PushSwap.git
cd PushSwap

# Compiler push_swap et le visualiseur
make

# Compiler uniquement push_swap
make push_swap

# Compiler le checker (bonus)
make bonus

# Compiler tout (push_swap + checker + visualiseur)
make both

🚀 Utilisation

Push Swap

./push_swap [nombres...]

Le programme affiche la liste des opérations nécessaires pour trier les nombres.

Exemple :

./push_swap 3 2 1 5 4

Sortie :

pb
pb
sa
pa
pa

Arguments

• Nombres séparés par des espaces : ./push_swap 4 67 3 87 23
• Chaîne de caractères : ./push_swap "4 67 3 87 23"
• Les nombres doivent être des entiers dans la plage des int
• Pas de doublons autorisés
• ⚠️ Important : Utilisez entre 0 et 1000 nombres maximum pour éviter des temps de calcul trop longs

📜 Règles

Le programme peut utiliser les opérations suivantes :

Opérations de swap

• sa : swap a - Échange les 2 premiers éléments de la pile A
• sb : swap b - Échange les 2 premiers éléments de la pile B
• ss : swap a et b en même temps

Opérations de push

• pa : push a - Prend le premier élément de B et le met sur A
• pb : push b - Prend le premier élément de A et le met sur B

Opérations de rotation

• ra : rotate a - Décale tous les éléments de A vers le haut (le premier devient le dernier)
• rb : rotate b - Décale tous les éléments de B vers le haut
• rr : rotate a et b en même temps

Opérations de rotation inverse

• rra : reverse rotate a - Décale tous les éléments de A vers le bas (le dernier devient le premier)
• rrb : reverse rotate b - Décale tous les éléments de B vers le bas
• rrr : reverse rotate a et b en même temps

✅ Checker

Le programme checker permet de vérifier si une séquence d'opérations trie correctement une pile.

Utilisation

./checker [nombres...]

Le programme lit les opérations depuis l'entrée standard et affiche :

• OK si la pile est triée
• KO si la pile n'est pas triée ou si une erreur survient
• Error si les arguments sont invalides

Exemple

./push_swap 3 2 1 | ./checker 3 2 1
# Sortie: OK

echo -e "pb\npa" | ./checker 3 2 1
# Sortie: OK

echo -e "sa\nsa" | ./checker 3 2 1
# Sortie: KO

🎨 Visualiseur

Le projet inclut un visualiseur graphique pour voir le tri en action !

Lancement

cd visualizer/build
./push_swap_visualizer

Fonctionnalités

• Visualisation en temps réel du tri
• Animation des opérations
• Interface graphique intuitive
• Contrôles pour pause/lecture/vitesse

💡 Astuce : Pour une visualisation optimale, utilisez entre 10 et 100 nombres. Au-delà de 1000 nombres, le calcul peut devenir très long.

📊 Exemples

Exemple 1 : Petite pile (3 nombres)

./push_swap 2 1 3

Sortie :

sa

Exemple 2 : Pile moyenne (5 nombres)

./push_swap 5 4 3 2 1

Exemple 3 : Grande pile (100 nombres)

ARG=$(seq 1 100 | shuf | tr '\n' ' ')
./push_swap $ARG | wc -l

🧪 Tests

Test de base

# Test avec 3 nombres
./push_swap 2 1 3 | ./checker 2 1 3

# Test avec 5 nombres
./push_swap 5 4 3 2 1 | ./checker 5 4 3 2 1

# Test avec 100 nombres aléatoires
ARG=$(seq 1 100 | shuf | tr '\n' ' ')
./push_swap $ARG | ./checker $ARG

Compter les opérations

# Pour 100 nombres
ARG=$(seq 1 100 | shuf | tr '\n' ' ')
./push_swap $ARG | wc -l

# Pour 500 nombres
ARG=$(seq 1 500 | shuf | tr '\n' ' ')
./push_swap $ARG | wc -l

Test d'erreurs

# Doublon
./push_swap 1 2 3 3
# Sortie: Error

# Non-numérique
./push_swap 1 2 abc
# Sortie: Error

# Dépassement d'int
./push_swap 1 2 2147483648
# Sortie: Error

🧹 Nettoyage

# Nettoyer les fichiers objets
make clean

# Nettoyer tout (exécutables inclus)
make fclean

# Recompiler
make re

📝 Structure du projet

PushSwap/
├── Makefile                 # Makefile principal
├── README.md               # Ce fichier
├── includes/               # Fichiers d'en-tête
│   ├── push_swap/         # Headers de push_swap
│   └── checker/           # Headers du checker
├── srcs/                  # Fichiers sources
│   ├── push_swap/         # Sources de push_swap
│   └── checker/           # Sources du checker
└── visualizer/            # Visualiseur graphique
    ├── src/
    ├── include/
    └── dependencies/

📄 Licence

Ce projet fait partie du cursus de l'école 42.

---

⭐ N'hésitez pas à mettre une étoile si ce projet vous a été utile !