This project has been created as part of the 42 curriculum by mju-ferr.
Push_swap is a sorting algorithm project that challenges you to sort data in a stack using a limited set of instructions, with the goal of achieving the lowest possible number of operations.
The project provides two stacks (A and B) and 11 specific operations to manipulate them. Stack A starts with a random set of unique integers (positive and/or negative), while Stack B begins empty. The objective is to sort Stack A in ascending order with the smallest number on top.
This project is an exercise in algorithm complexity, optimization, and understanding different sorting strategies. You must choose and implement the most appropriate algorithms for different dataset sizes to meet strict performance benchmarks.
- Two stacks: Stack A (initially filled with numbers) and Stack B (initially empty)
- 11 operations: swap, push, rotate, and reverse rotate operations
- Goal: Sort Stack A in ascending order with minimum operations
- Challenge: Different algorithms perform better depending on the number of elements
To compile the mandatory part:
makeThis will:
- Compile your libft library (from the
libft/directory) - Compile all source files
- Create the
push_swapexecutable
Other Makefile rules:
make clean # Remove object files
make fclean # Remove object files and executables
make re # Rebuild everything from scratch
make bonus # Compile the bonus checker program (if implemented)./push_swap <numbers>The program accepts integers as arguments (space-separated):
./push_swap 3 2 1 0Or as a single quoted string:
./push_swap "3 2 1 0"Or mixed formats:
./push_swap "3 2" 1 0Accepted integer formats:
- Standard integers:
42,-42,+42 - Leading zeros:
007(interpreted as 7) - Multiple signs:
--42(double negative = 42),---42(= -42)
These are all mathematically valid integer representations.
The program outputs a series of operations to stdout, one per line:
$ ./push_swap 2 1 3
saIf the stack is already sorted or no arguments are provided, no output is displayed.
In case of error, the program displays "Error" followed by a newline on stderr and exits:
$ ./push_swap 1 2 a
Error
$ ./push_swap 1 2 2
ErrorErrors include:
- Non-integer arguments
- Integer overflow (values outside INT_MIN to INT_MAX range)
- Duplicate values
You can verify the sorting using the provided checker (if implemented as bonus):
ARG="4 67 3 87 23"
./push_swap $ARG | ./checker $ARGThe checker will output:
OKif the operations correctly sort the stackKOif the stack is not sorted or Stack B is not emptyErrorif invalid operations or arguments
This implementation uses a hybrid approach that selects the optimal algorithm based on the number of elements to sort:
Hardcoded optimal solutions
For very small sets, the most efficient approach is to use pre-determined optimal sequences:
- 2 numbers: Maximum 1 operation (
saif needed) - 3 numbers: Maximum 2 operations (case analysis)
- 4 numbers: ~8-10 operations (isolate minimum, sort 3, push back)
- 5 numbers: ~12 operations (isolate 2 minimums, sort 3, push back)
These hardcoded solutions guarantee the absolute minimum number of operations.
Turk/Chunk Algorithm with Cost Optimization
For larger sets, the implementation uses a chunk-based algorithm with intelligent cost calculation:
-
Index Normalization
- Map all values to normalized indices (0 to N-1)
- Simplifies comparisons and algorithm logic
- Maintains sorting relationships
-
Chunking Strategy
- Divide the range into chunks based on size:
- 100 elements: ~5 chunks (20 elements per chunk)
- 500 elements: ~12-15 chunks (33-40 elements per chunk)
- Push elements to Stack B in chunk order
- Keep larger elements toward the top of Stack B
- Divide the range into chunks based on size:
-
Cost Calculation
- For each element in Stack B, calculate:
- Cost to bring element to top of B
- Cost to rotate Stack A to target position
- Total cost = cost_a + cost_b
- Consider both rotation directions (ra vs rra)
- Use combined operations (rr, rrr) when both stacks rotate in same direction
- For each element in Stack B, calculate:
-
Greedy Selection
- Choose element with minimum total cost
- Execute optimal sequence of operations
- Push element from B to A at target position
- Repeat until B is empty
-
Final Rotation
- Rotate Stack A to position minimum at top
- Stack is now sorted
- Dual operations: Use
rrandrrrwhen both stacks need rotation - Direction selection: Choose cheaper rotation direction (rotate vs reverse rotate)
- Look-ahead: Maintain partial ordering in Stack B during push phase
- Cost minimization: Always select the cheapest move at each step
The algorithm meets the following benchmark requirements:
| Elements | Operations | Status |
|---|---|---|
| 3 | ≤ 3 | ✓ Met |
| 5 | ≤ 12 | ✓ Met |
| 100 | < 700 | ✓ Met |
| 500 | ≤ 5500 | ✓ Met |
Alternative acceptable combinations:
- 100 numbers: < 1100 ops AND 500 numbers: < 8500 ops
- 100 numbers: < 700 ops AND 500 numbers: < 11500 ops
- 100 numbers: < 1300 ops AND 500 numbers: < 5500 ops
To test with random numbers:
# Test 100 numbers
ARG=$(seq 1 100 | shuf | tr '\n' ' ')
./push_swap $ARG | wc -l
# Test 500 numbers
ARG=$(seq 1 500 | shuf | tr '\n' ' ')
./push_swap $ARG | wc -lTo verify correctness:
ARG=$(seq 1 100 | shuf | tr '\n' ' ')
./push_swap $ARG | ./checker_OS $ARG
# Should output: OKpush_swap/
├── Makefile # Build configuration
├── README.md # This file
├── includes/
│ ├── push_swap.h # Main header file
│ └── push_swap_bonus.h # Bonus header
├── srcs/
│ ├── main.c # Entry point and algorithm router
│ ├── parser.c # Argument parsing (parse_arguments + 2 static helpers)
│ ├── validate.c # Number validation (is_valid_number, ft_atol, is_int_range, has_duplicates)
│ ├── error.c # Error handling
│ ├── stack_init.c # Stack initialization (init_stack_a)
│ ├── stack_utils.c # Basic stack operations (new, size, last, add)
│ ├── stack_find.c # Stack search (min, max, is_sorted)
│ ├── position.c # Position assignment
│ ├── index.c # Index normalization
│ ├── operations_swap.c # sa, sb, ss operations
│ ├── operations_push.c # pa, pb operations
│ ├── operations_rotate.c # ra, rb, rr operations
│ ├── operations_reverse.c # rra, rrb, rrr operations
│ ├── sort_small.c # Hardcoded sorts for ≤5 elements
│ ├── sort_large.c # Chunk algorithm for large sets
│ ├── cost.c # Cost calculation and optimization
│ └── free.c # Memory cleanup
├── srcs_bonus/
│ ├── checker_bonus.c # Bonus: operation validator
│ └── ... # Other bonus files
├── libft/
│ ├── Makefile # Libft build configuration
│ ├── libft.h # Libft header
│ ├── *.c # Libft source files
│ └── ft_printf/ # Custom printf implementation
│ ├── ft_printf.h # ft_printf header
│ ├── ft_printf.c # Main printf function + format handler
│ ├── ft_printf_char.c # Character/string output (ft_putchar, ft_putstr)
│ ├── ft_printf_nbr.c # Number output (ft_putnbr, ft_putnbr_unsigned)
│ └── ft_printf_hex.c # Hex/pointer output (ft_puthex, ft_putptr)
Note: Validation functions are in a separate file (validate.c) from parsing (parser.c)
to comply with the 42 Norm limit of 5 functions per file.
The program can output the following operations:
- sa: Swap the first 2 elements at the top of Stack A
- sb: Swap the first 2 elements at the top of Stack B
- ss: Execute
saandsbsimultaneously
- pa: Take the top element from B and put it on top of A
- pb: Take the top element from A and put it on top of B
- ra: Shift all elements of Stack A up by 1 (first becomes last)
- rb: Shift all elements of Stack B up by 1 (first becomes last)
- rr: Execute
raandrbsimultaneously
- rra: Shift all elements of Stack A down by 1 (last becomes first)
- rrb: Shift all elements of Stack B down by 1 (last becomes first)
- rrr: Execute
rraandrrbsimultaneously
The project uses a linked list implementation for the stacks:
typedef struct s_stack
{
int value; // Original value from input
int index; // Normalized index (0 to N-1)
int pos; // Current position in stack
int target_pos; // Target position for optimization
int cost_a; // Cost to move in Stack A
int cost_b; // Cost to move in Stack B
struct s_stack *next; // Pointer to next node
} t_stack;- Dynamic memory allocation: Efficient use of memory
- O(1) push/pop operations: Optimal for stack operations
- Position tracking: Enables cost calculation
- Cost caching: Stores movement costs for optimization
- All heap-allocated memory is properly freed
- No memory leaks (verified with valgrind)
- Proper error handling with cleanup on failures
- Safe handling of malloc failures
The project includes a custom ft_printf implementation in libft/ft_printf/ for formatted output:
Supported format specifiers:
%c- Single character%s- String%p- Pointer address%d,%i- Signed integer%u- Unsigned integer%x,%X- Hexadecimal (lowercase/uppercase)%%- Literal percent sign
Usage in operations:
// Operations use ft_printf for output
if (print)
ft_printf("sa\n"); // Instead of write(1, "sa\n", 3)- 42 Norm: Fully compliant with the 42 coding standard
- No global variables: All state passed through function parameters
- Function limits: Maximum 25 lines per function, 4 parameters
- Compilation flags:
-Wall -Wextra -Werror
- Wikipedia: Sorting Algorithm - General overview of sorting algorithms and their complexities
- GeeksforGeeks: Sorting Algorithms - Detailed explanations with examples
- Big-O Cheat Sheet - Algorithm complexity reference
- Wikipedia: Stack (abstract data type) - Understanding stack operations
- Linked List Tutorial - Implementation in C
- Khan Academy: Algorithms - Algorithm fundamentals
- Visualgo - Algorithm visualization tool
- Push_swap Visualizer - Visual debugging tool
- Push_swap Tester - Automated testing script
- 42 Intranet Project Page - Official requirements and checker program
- valgrind: Memory leak detection (
valgrind --leak-check=full ./push_swap) - norminette: 42 Norm checker
- gdb: GNU debugger for C programs
This project utilized AI assistance (Claude Code and ChatGPT) during development to enhance productivity and learning.
- Researching different sorting algorithms suitable for stack operations
- Understanding chunk-based sorting strategies
- Analyzing algorithm complexity and optimization techniques
- Comparing different approaches (Radix sort, Quick sort adapted, Chunk sort)
- Organizing project structure and file layout
- Creating implementation checklists and development roadmap
- Breaking down complex tasks into manageable steps
- Designing data structures for efficient operations
- Identifying potential edge cases and error scenarios
- Suggesting optimization strategies for benchmark improvement
- Reviewing cost calculation logic
- Analyzing memory management patterns
- Generating comprehensive documentation structure
- Creating detailed README sections
- Writing clear explanations of algorithm approaches
- Organizing technical documentation
- Test cases: AI suggested comprehensive test scenarios and edge cases
- Benchmark scripts: Assisted in creating automated testing scripts
- Validation approach: Helped design the testing and verification workflow
- Cost calculation: AI provided insights on efficient cost calculation methods
- Chunk sizing: Assisted in determining optimal chunk sizes for different input sizes
- Operation batching: Suggested strategies for combining operations (rr, rrr, ss)
While AI assisted in research, planning, and initial code structure, all final code was reviewed, understood, modified, and tested by the developer. The developer takes full responsibility for the implementation and can explain every part of the codebase during evaluation. AI was used as a learning and productivity tool, not as a replacement for understanding.
mju-ferr
- 42 Network Student
- Project: Push_swap
- Version: 1.0
This project is part of the 42 School curriculum. Code is provided for educational purposes.
- 42 Network for the project design and learning framework
- Peers and the 42 community for discussions and peer learning
- Online resources and documentation for algorithm understanding
- AI tools for development assistance and documentation