This project has been created as part of the 42 curriculum by gbitar, pabdalla
The push_swap project is a sorting algorithm challenge from the 42 curriculum.
The goal is to sort a stack of integers in ascending order using a limited set of operations (sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr) and to do so with the minimum number of moves possible.
- Algorithmic thinking and optimization
- Efficient memory and pointer usage in C
- Understanding of stacks and linked lists
- Handling edge cases and input validation
- push_swap - outputs a sequence of operations to sort the stack.
- checker – verifies whether a sequence of operations correctly sorts the input.
To compile the project:
make
This will create the executable push_swap
(The project uses libftprintf, we need to compile them first using make in the ft_printf's directory)
Run push_swap with a list of integers as arguments:
./push_swap 4 7 2 9 6 0 1 44 8 -1
Optional strategy selectors:
-
--simple→ O(n²) algorithm -
--medium→ O(n√n) algorithm -
--complex→ O(n log n) algorithm -
--adaptive→ adaptive algorithm based on disorder (default)
The --bench flag in push_swap only affects the output of metrics — it does not change the sorting itself.
You get metrics printed to stderr, while the actual operation list is still printed to stdout.
- Disorder (%) – measures how unordered the input stack is before sorting.
- 0% → fully sorted
- 100% → worst possible disorder
- Strategy used – indicates which algorithm was chosen:
- Simple (O(n²))
- Medium (O(n√n))
- Complex (O(n log n))
- Adaptive (dynamically selected)
-
Total number of operations – counts all push_swap instructions generated to sort the input.
-
Count of each operation type – for detailed analysis:
sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr
The program will output the sequence of operations needed to sort the stack.
To verify your solution using the checker:
./push_swap 4 7 2 9 6 0 1 44 8 -1 | ./checker 4 7 2 9 6 0 1 44 8 -1
The checker will output OK if the sequence sorts the stack correctly, or KO otherwise.
To change the permission of the checker:
chmod +x checker_linux
Errors are reported as:
Error
Examples of invalid input:
- Non-integer argument
- Duplicate integers
- Invalid operation in checker
During the development of this project, the following resources were consulted for learning and understanding concepts:
- YouTube tutorials – to better understand stack operations, sorting strategies, and algorithmic thinking.
- Peer discussions – shared ideas on sorting strategies and debugging approaches.
- GeeksforGeeks articles – for explanations on sorting algorithms, radix sort, and stack manipulations.
- AI assistance (ChatGPT) – used only to clarify concepts, explain algorithms, memory management, and C pointers. No implementation code from AI was used; all implementations are original.
- All code in this project, including the algorithms (
simple,medium,complex,adaptive), is written from scratch by the authors. - AI or external resources were consulted only for educational purposes and to enhance understanding, not to copy code.
Several strategies were implemented to optimize the number of moves:
-
Simple algorithm – for small numbers of elements (<=5), using minimal moves with direct comparisons.
- Complexity: O(n²)
- How it works:
- Finds the minimum element in stack A.
- Rotates the stack (ra or rra) to bring the minimum to the top.
- Pushes it to stack B (pb) until stack A is empty.
- Moves all elements back to stack A (pa).
-
Medium algorithm – divides the stack into chunks and pushes them to stack B strategically, then moves them back.
- Complexity: O(n√n)
- How it works:
- Creates a sorted copy of stack A.
- Divides elements into chunks based on size.
- Indexes nodes according to the sorted copy.
- Pushes chunks to stack B strategically.
- Retrieves elements back to stack A in sorted order.
-
Complex algorithm - Radix sort adaptation using stack indices
- Complexity: O(n log n)
- How it works:
- Indexes nodes based on sorted order.
- Determines the number of bits required for radix sorting.
- Applies a radix-like bitwise sorting, pushing and rotating stacks strategically.
- Reconstructs sorted stack A efficiently.
-
Adaptive algorithm - Chooses a sorting method based on disorder metric (0–1) of input:
- How it works:
- Calculates the disorder percentage of the stack.
- Chooses:
- Low disorder (<0.2) → O(n)
- Medium disorder (0.2–0.5) → O(n√n)
- High disorder (≥0.5) → O(n log n)
- Designed to optimize operation count dynamically.