66 lines
1.9 KiB
Markdown
66 lines
1.9 KiB
Markdown
# Push_swap
|
|
|
|
## Description
|
|
Push_swap est un projet de l'École 42 qui consiste à trier une pile de nombres entiers avec un nombre limité d'opérations. L'objectif est de développer un algorithme efficace utilisant deux piles et un set d'opérations définies.
|
|
|
|
## Objectif
|
|
Trier une pile A en utilisant une pile auxiliaire B avec le minimum d'opérations possibles.
|
|
|
|
## Opérations autorisées
|
|
- **sa** : swap les 2 premiers éléments de A
|
|
- **sb** : swap les 2 premiers éléments de B
|
|
- **ss** : sa et sb en même temps
|
|
- **pa** : push le premier élément de B vers A
|
|
- **pb** : push le premier élément de A vers B
|
|
- **ra** : rotate A (premier devient dernier)
|
|
- **rb** : rotate B (premier devient dernier)
|
|
- **rr** : ra et rb en même temps
|
|
- **rra** : reverse rotate A (dernier devient premier)
|
|
- **rrb** : reverse rotate B (dernier devient premier)
|
|
- **rrr** : rra et rrb en même temps
|
|
|
|
## Algorithmes implémentés
|
|
- **Tri simple** pour 3-5 éléments
|
|
- **Algorithme LIS** (Longest Increasing Subsequence)
|
|
- **Radix sort** adapté aux piles
|
|
- **Optimisations** pour réduire les mouvements
|
|
|
|
## Technologies utilisées
|
|
- **Langage** : C
|
|
- **Structures de données** : Listes chaînées
|
|
- **Algorithmes** : Tri, optimisation
|
|
- **Parsing** : Validation des arguments
|
|
|
|
## Installation
|
|
```bash
|
|
git clone <repository-url>
|
|
cd Push_swap
|
|
make
|
|
./push_swap 4 67 3 87 23
|
|
```
|
|
|
|
## Objectifs de performance
|
|
- **3 nombres** : maximum 3 opérations
|
|
- **5 nombres** : maximum 12 opérations
|
|
- **100 nombres** : moins de 700 opérations (5 points)
|
|
- **500 nombres** : moins de 5500 opérations (5 points)
|
|
|
|
## Bonus : Checker
|
|
Programme qui vérifie si une séquence d'opérations trie correctement la pile.
|
|
|
|
```bash
|
|
./checker 4 67 3 87 23
|
|
sa
|
|
pb
|
|
rrr
|
|
# Affiche "OK" si trié, "KO" sinon
|
|
```
|
|
|
|
## Compétences développées
|
|
- Algorithmes de tri avancés
|
|
- Optimisation de complexité
|
|
- Structures de données
|
|
- Analyse d'algorithmes
|
|
|
|
## Auteur
|
|
Alexandre Pommier (apommier) - École 42 |