From ea160e2d3391e8a71af480146a3402a02c442dcb Mon Sep 17 00:00:00 2001 From: = <=> Date: Fri, 19 Dec 2025 14:01:47 +0100 Subject: [PATCH] English readme and removed unused file --- README.md | 106 +++------ input.txt | 655 ------------------------------------------------------ 2 files changed, 34 insertions(+), 727 deletions(-) delete mode 100644 input.txt diff --git a/README.md b/README.md index c5e06eb..247fdd6 100644 --- a/README.md +++ b/README.md @@ -1,110 +1,72 @@ *This project has been created as part of the 42 curriculum by agilliar, clefrere.* -# PUSH_SWAP (FR) +# PUSH_SWAP -## Description : +## Description: -L'objectif de push_swap est de trier une liste d'int. +The goal of push_swap is to sort a list of integers. -Pour cela, nous avons deux stacks (a et b), une liste de valeurs et des opérations permettant de manipuler les stacks. +To do so, we start with two stacks, a and b, with the list elements on a, and a set of operations to manipulate stacks. -**Pour faire le tri de ces éléments, il est nécessaire d'utiliser 4 algorithmes distinct, qui pourront être choisi lors de l'exécution du programme grâce au flag correspondant : --simple / --medium / --complex / --adaptive. Plus la complexité de l'algorithme est élevée, plus la liste va se trier rapidement.** +**To achieve said sort, 4 distinct algorithms are used, which shall be chosen from at runtime using the flags: `--simple` `--medium` `--complex` `--adaptive`, defaulting to adaptive.** -Certains algorithmes utilisent un split sort (par agilliar), tri récursif similaire a quick sort, partitionnant en n chunks, en extrayant deux chunks par passages sur la liste. +Some algorithms use "splitsort" (created by agilliar), a recursive sort akin to quicksort, partitionning in a set amount of chunks each step, extracting chunks two at a time by iterating over the whole list. -Les tris des petites tailles du split sort sont effectuées via une table pré calculée d'instructions optimal. +Small leaf sorts of splitsort use a pre-computed lookup table of optimal sort instructions. -Un optimiser a été ajouté pour simplifier certaines combinaisons d'opérations triviales. +An optimizer was added in order to shorten trivial operation combinations, which result in pretty significant performance improvements. +### Simple algorithm (O(n^2)): +Our implementation uses **selection sort**. -### Algorithme simple (O(n^2)): +We repeatedly rotate `a` until the greatest element is found, which is then pushed onto `b`. -Nous avons choisi d'utiliser le **selction sort**. +This is repeated until `a` is empty at which point every element of `b` is pushed back onto `a`, sorting it. -Nous faisons une rotation du stack `a` jusqu'à trouver le plus petit élément, qui sera push sur `b`. +This algorithm was chosen for its simplicity and relative effiiency. -Une fois `a` vide, l'ensemble de `b` sera push sur `a` pour remettre l'ensemble des éléments dans le bon ordre. +### Medium algorithm (O(n^1.5)) -Cet algorithme a été choisi car celui-ci est facile à mettre en place et à comprendre. +This algorithm uses **splitsort** with its chunk count proportional to the square root of n. +It was chosen for its excellent performance whilst reaching O(n^1.5) complexity. -### Algorithme intermédiaire (O(n^1.5)) +### Complex algorithm (O(n log n)) -L'algorithme intermédiaire est un **splitsort** avec le nombre de chunks proportionnel a la racine de la taille de la liste, ce qui permet d'avoir la complexité voulue. - -Cet algorithme a été choisi car il permet d'avoir l'excellente performance de splitsort tout en restant O(n^1.5). - - - -### Algorithme Complexe (O(n log n)) - -Pour l'algorithme complexe, nous avons choisi d'utiliser le **split sort** avec un nombre de chunks constant (5). - -Il se rapproche donc d'un quicksort tout en étant plus performant, et atteint la complexité demandée. +For this, we have chosen to also use **splitsort**, this time with a constant number of chunks (5, optimal found through trial and error). +Thus it is similar to quicksort while being much better suited to stack sorting, thanks to that chunks count. ### Algorithme adaptatif -Nous partons du principe que le "low disorder" est une erreur et que la complexité attendue est de n^2, car le problème est impossible sinon (voir avec agilliar pour le détail). - -Pour notre implémentation, nous choisissons simplement l'un des algorithmes précédents. +We assume the "low disorder" requirement is a type that should have been "O(n^2)", as it is otherwise provably impossible (see with agilliar for details). -### Le bench - -Le bench est un flag supplémentaire (`--bench`) qui va permettre d'afficher des informations supplémentaires lors de l'exécution du programme : - -**Le desorde** - -**La strategie (algorithme utilise)** - -**Le nombre total d'opérations avant et après optimiser** - -**Le nombre de fois que chaque opération a été utilisé** +Our implementation simply chooses between the aforementionned algorithms, using the flawed albeit required disorder heuristic. +### Bench mode +The bench mode is an extra flag (`--bench`) which enables outputting extra information on the standard out, notably: +* The computed disorder +* The chosen sorting strategy +* The total and individual operation count, both before and after the optimizer ## Instructions -1) Programme - -a) Faire `make` +### Program -b) Sans flag : `./push_swap 2 1 3 6 5 8` +Simply run `make`, then give the initial list as arguments, optionally with flags. -c) Avec un flag d'algorithme : `./push_swap --simple 2 1 3 6 5 8` - -d) Avec le flag bench : `./push_swap --bench 2 1 3 6 5 8` - -e) Avec bench + algorithme : `./push_swap 2 1 3 6 5 8 --bench --simple` - -3) Bonus : +### Bonus -a) Faire `make bonus` - -b) `INPUT=$(shuf -i 1-100)` - -c) `./push_swap $(echo $INPUT) | ./checker $(echo $INPUT)` - -4) Utiliser le testeur : - -a) Télécharger le checker - -b) `INPUT=$(shuf -i 1-100)` - -c) `./push_swap $(echo $INPUT) | ./checker_linux $(echo $INPUT)` - - +Run `make bonus`, then give the initial list as arguments. +The program will then check if the given operations in standard in do in fact sort the list. ## Ressources -Pour la compréhension de sélection sort : - -**Wikipedia** - -**GeeksforGeeks** +clefrere used *Wikipedia* and *GeeksForGeeks*, in order to understand a broad family of algorithms. -L'IA n'a pas été utilisée pour ce projet. +agilliar mostly used *wikipedia* to browse for preexisting fitting algorithms, though none were found to be a good fit for high performance. -# PUSH_SWAP (ENG) \ No newline at end of file +No AI was used in this project, except for initial shallow research, for which it proved to be unhelpful, being sublty wrong in multiple instances. diff --git a/input.txt b/input.txt deleted file mode 100644 index 6ee4a92..0000000 --- a/input.txt +++ /dev/null @@ -1,655 +0,0 @@ -ra -ra -pb -rr -ra -ra -ra -pb -pb -ra -pb -rb -pb -rr -pb -rb -pb -pb -pb -ra -ra -pb -ra -ra -ra -pb -rr -pb -rr -ra -ra -pb -pb -rb -pb -pb -rr -pb -pb -pb -rr -ra -ra -ra -ra -ra -ra -pb -rb -pb -rr -pb -pb -pb -ra -ra -ra -ra -pb -rr -ra -pb -ra -ra -pb -pb -rb -pb -rb -pb -ra -pb -rb -pb -rr -ra -ra -ra -ra -ra -ra -ra -pb -rb -pb -ra -ra -ra -ra -ra -ra -ra -ra -pb -rr -ra -pb -rr -ra -ra -ra -ra -pb -pb -pb -pb -rra -rra -rra -rb -pb -rra -pb -rra -rb -pb -rra -rb -pb -rra -rra -rb -pb -rra -pb -rra -rb -pb -rra -pb -rra -pb -rra -rra -rra -rb -pb -rra -rra -rb -pb -rra -rra -rra -rb -pb -rra -rb -pb -rra -pb -rra -rb -pb -rra -pb -rra -rb -pb -rra -pb -rra -rb -pb -rra -rb -pb -rra -pb -rra -pb -rra -pb -rra -rra -pb -rra -pb -rra -rra -pb -rra -rra -rra -pb -rra -rb -pb -rra -rra -rra -rb -pb -rra -rb -pb -rra -pb -rra -rra -rra -rra -rb -pb -rra -pb -rra -rb -pb -rra -rb -pb -rra -pb -rra -pb -rra -rb -pb -rra -rb -pb -rra -rra -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pb -pa -pa -rr -rb -rb -rb -rb -pa -rr -rb -pa -rr -pa -rb -rb -rb -pa -pa -ra -pa -rb -sa -pb -sa -pb -sa -pa -pa -rra -rra -pb -rra -pb -rra -sa -pa -pa -rrb -pa -rrb -pa -rrb -pa -rrb -pa -ra -rrb -pa -rrb -rrb -pa -ra -rrb -rrb -pa -ra -rrb -pa -ra -rrb -rrb -pb -sa -pb -ss -pa -sa -pa -sa -rra -pb -rra -rra -sa -rra -pa -pa -pa -pa -pa -pb -pb -ss -pa -sa -pa -pa -ra -pa -pa -rb -pa -rb -rb -rb -rb -rb -rb -pa -rb -rb -rb -rb -rb -pa -ra -pa -ra -pa -ra -pb -sa -pb -sa -pa -sa -pa -rra -rra -rra -pb -rra -sa -pa -rrb -pa -rrb -rrb -pa -ra -rrb -rrb -pa -ra -rrb -pa -ra -rrb -pa -rrb -rrb -pa -rrb -pa -ra -rrb -pa -rrb -pb -sa -pb -sa -pa -sa -pa -rra -pb -rra -rra -sa -pa -rra -pa -pa -pa -pa -sa -pb -sa -pa -sa -pa -rb -rb -rb -pa -rr -rb -pa -rr -rb -pa -rb -pa -rr -pa -rr -pa -rb -pa -rb -pb -sa -pb -ss -pa -sa -pa -sa -rra -pb -rra -rra -pa -rrr -pa -rrb -pa -ra -rrb -pa -ra -rrb -pa -ra -rrb -pa -rrb -rrb -rrb -rrb -pa -ra -rrb -pa -rrb -pa -rrb -sa -pb -sa -pb -sa -pa -pa -rra -pb -rra -rra -pa -rra -pa -pa -pa -pa -pb -pb -ss -pa -sa -pa -sa -rb -pa -rr -pa -rb -rb -rb -rb -rb -pa -pa -rb -pa -rr -pa -rr -rb -rb -pa -ra -pa -pb -pb -ss -ra -pa -sa -pa -rra -rra -rra -pb -rra -sa -pa -rrr -pa -rrb -pa -ra -rrb -pa -rrb -rrb -pa -rrb -rrb -rrb -pa -ra -rrb -pa -ra -rrb -rrb -pa -rrb -pa -ra -pb -pb -ss -pa -sa -pa -sa -rra -rra -pb -rra -rra -pa -pa -pa -pa -pa -sa -pb -sa -pb -ss -pa -sa -pa -rb -pa -rb -pa -rb -pa -rr -rb -pa -rr -pa -rb -rb -rb -rb -rb -rb -pa -ra -pa -pa -ra -pb -pb -ss -ra -pa -sa -pa -rra -rra -rra -pb -rra -sa -pa -rrr -pa -rrb -pa -ra -rrb -rrb -pa -ra -rrb -rrb -rrb -pa -rrb -rrb -pa -ra -rrb -pa -ra -rrb -pa -rrb -pa -sa -rra -rra -pb -rra -pb -rra -sa -pa -pa -pa -pa -pa -pa -- 2.51.0