This project has been created as part of the 42 curriculum by bpavlows
The push_swap project is a very simple and highly effective algorithm project: data must be sorted.
You have at your disposal a set of integer values, 2 stacks, and a set of instructions to manipulate both stacks.
The goal? Write a program in C called push_swap which calculates and displays on the standard output the smallest program, made of Push Swap language instructions, that sorts the integers received as arguments.
The Challenge:
- Use the lowest possible number of moves.
- Handle complex error management (non-integers, duplicates, overflow).
- Sort 100 numbers in < 700 moves.
- Sort 500 numbers in < 5500 moves.
| Code | Instruction | Action |
|---|---|---|
sa |
swap a | Swap the first 2 elements at the top of stack A. |
sb |
swap b | Swap the first 2 elements at the top of stack B. |
ss |
swap a + swap b | sa and sb at the same time. |
pa |
push a | Take the first element at the top of B and put it at the top of A. |
pb |
push b | Take the first element at the top of A and put it at the top of B. |
ra |
rotate a | Shift up all elements of stack A by 1. |
rb |
rotate b | Shift up all elements of stack B by 1. |
rr |
rotate a + rotate b | ra and rb at the same time. |
rra |
reverse rotate a | Shift down all elements of stack A by 1. |
rrb |
reverse rotate b | Shift down all elements of stack B by 1. |
rrr |
reverse rotate a + reverse rotate b | rra and rrb at the same time. |
This project uses a Greedy Algorithm (often referred to as the "Turk Algorithm" in the 42 community).
The Core Concept: Cost Analysis Instead of thinking about the whole list, the algorithm decides the next move based on the immediate "cost" of moving each element.
- Each number in Stack A calculates: "How many moves would it take to get me to the correct position in Stack B?"
- The algorithm compares the cost of all numbers.
- The number with the cheapest cost is chosen and moved.
The Steps:
- Push to B: Move all numbers from Stack A to Stack B, leaving only 3 numbers in A. (Pre-sorting can be applied here).
- Sort Three: Easily sort the remaining 3 numbers in Stack A.
- Calculate Costs: For every node in Stack B, calculate the cost to push it back to the correct spot in Stack A.
- Cost includes rotations needed in both stacks (
ra,rb,rr,rra,rrb,rrr).
- Cost includes rotations needed in both stacks (
- Move Cheapest: Execute the move for the element with the lowest cost.
- Repeat: Do this until Stack B is empty.
- Final Adjust: Rotate Stack A until the smallest number is at the top.
Data Structure:
I used a Doubly Linked List to store the stacks. This allows easy access to the next and prev nodes, which is crucial for calculating the cost of reverse rotations (rra/rrb).
1. Compilation To compile the program, run the Makefile:
makeRun the program passing a list of integers as arguments
./push_swap <value1> <value2> <value3> ... <valueN>If you need 100 random values:
ARG=$(shuf -i 1-100 | tr '\n' ' '); ./push_swap $ARGor 500 values:
ARG=$(shuf -i 1-500 | tr '\n' ' '); ./push_swap $ARGOutput
- The program will output the list of operations needed to sort the list.
Erros: The program handles errors such as:
- Non-numeric arguments.
./push_swap 5 4 3 * 2 1or:
./push_swap 5 4 3 "i" 2 1- Duplicate numbers.
./push_swap 5 4 3 1 2 1- Numbers greater than INT_MAX or smaller than INT_MIN.
./push_swap 5 4 2147483648or:
./push_swap 5 4 -2147483649- If you need check using the checker_linux, use:
ARG=$"5 3 4 1 2"; ./push_swap $ARG | checker_linux $ARG- If you need to use the Valgrind:
valgrind ./push_swap 5 4 1 2 3- For check the number of movements:
./push_swap 5 4 1 2 3 | wc -lBooks:
- Grokking Algorithms - Aditya Y. Bhargava
- Language C - Luis Damas
Websites:
GitHub with Guides:
Medium Blog Pages:
Visualizer:
Wikipedia:
AI: Gemini for learning sorts algorithms and linked lists, and how implement this on my code.