This project has been created as part of the 42 curriculum by yoben-ch and stelescu.
Push_swap is a sorting project developed at 42 School. The objective is to sort a stack of integers using only two stacks (a and b) and a restricted set of stack operations.
Unlike traditional sorting algorithms, the goal is not only to obtain a sorted result but also to minimize the number of Push_swap operations generated.
This project implements the four strategies required by the subject:
- Simple Strategy — O(n²)
- Medium Strategy — O(n√n)
- Complex Strategy — O(n log n)
- Adaptive Strategy — automatically selects the most appropriate algorithm according to the disorder index
The repository also includes the bonus checker program used to validate generated instruction sequences.
| Login | Contribution |
|---|---|
| yoben-ch | Input parsing and validation, option management, adaptive strategy, benchmark system, bonus implementation |
| stelescu | Medium algorithm implementation, small-sort algorithms (≤5 elements), argument splitting utilities |
| yoben-ch & stelescu | Complex algorithm design and implementation (Radix-based strategy), overall project architecture and testing |
Both contributors fully understand all algorithms and all parts of the codebase.
The program validates:
- Integer format
- INT_MIN / INT_MAX overflow
- Duplicate values
- Empty arguments
- Invalid flags
Invalid input produces:
Erroron stderr.
./push_swap 4 2 1 3or
./push_swap --adaptive 4 2 1 3Automatically chooses the best strategy.
./push_swap --simple 4 2 1 3Forces the O(n²) algorithm.
./push_swap --medium 4 2 1 3Forces the O(n√n) algorithm.
./push_swap --complex 4 2 1 3Forces the O(n log n) algorithm.
./push_swap --bench --adaptive 4 2 1 3Displays:
- Disorder percentage
- Selected strategy
- Complexity class
- Total operations
- Operation statistics
Benchmark information is printed on stderr as required by the subject.
makemake bonusmake cleanmake fcleanmake reThe project uses an array-based stack implementation:
typedef struct s_stack
{
int *tab;
int size;
int top;
} t_stack;Advantages:
- O(1) push/pop
- Low memory overhead
- Fast rotations
Before sorting, all values are normalized.
Example:
Original:
40 10 90 20
Normalized:
2 0 3 1
Normalization replaces each number with its rank in the sorted sequence.
Benefits:
- Removes dependence on actual integer values
- Simplifies comparisons
- Improves radix performance
Complexity:
Time: O(n²)
Space: O(n)
This preprocessing step is executed once before sorting.
The subject requires a disorder index.
Our implementation follows exactly the required inversion-count model.
For every pair:
(i, j) with i < j
we count an inversion whenever:
a[i] > a[j]
Formula:
disorder = inversions / total_pairs
Implementation:
int ft_disorder(t_stack *a)The result is stored as:
0 -> completely sorted
10000 -> maximum disorder
Equivalent to:
0.00% -> 100.00%
The adaptive algorithm chooses a sorting method according to the disorder index.
disorder < 20%
Uses:
Simple Strategy
Complexity:
O(n)
for nearly sorted inputs because most elements are already close to their final positions.
20% ≤ disorder < 50%
Uses:
Medium Strategy
Complexity:
O(n√n)
disorder ≥ 50%
Uses:
Complex Strategy
Complexity:
O(n log n)
The thresholds come directly from the subject requirements:
- Below 20% the stack is close to sorted.
- Between 20% and 50% partitioning techniques become more efficient.
- Above 50% highly disordered data benefits from radix-based processing.
These values provide a smooth transition between the required complexity classes.
We implemented a Selection-Style Extraction Sort.
The algorithm repeatedly searches for the next smallest normalized value.
Example:
A: 3 2 1 0
Move:
0 -> stack B
1 -> stack B
2 -> stack B
3 -> stack B
Then restore:
B -> A
Sorted result:
0 1 2 3
To extract each value we may need to rotate through a significant part of the stack.
For:
n elements
we may perform approximately:
n + (n-1) + (n-2) + ...
operations.
Therefore:
O(n²)
Push_swap operation complexity:
Worst case:
≈ n² / 2 rotations
+ 2n pushes
Thus:
O(n²)
Implemented by:
ft_medium()The stack is divided into:
√n partitions
Each partition contains approximately:
√n values
Example:
100 elements
Partitions:
0-9
10-19
20-29
...
90-99
Move each partition from A to B.
Elements belonging to the current partition are pushed immediately.
Other elements are rotated.
Rebuild the stack.
The largest available value is moved back first from B to A.
A cost function determines whether:
rb
or
rrb
is cheaper.
Number of partitions:
√n
Each partition requires scanning approximately:
n
elements.
Total Push_swap operations:
n × √n
Therefore:
O(n√n)
This satisfies the complexity class required by the subject.
Implemented by:
radix_sort()This algorithm was designed jointly by both contributors.
Traditional Push_swap radix implementations often use:
Base 2
We chose a dynamic base:
base = sqrt(n)Implemented in:
radix_base()Example:
n = 100
base = 10
Traditional binary radix requires:
log₂(n)
passes.
Using:
base = √n
reduces the number of digit levels while preserving efficient partitioning.
This creates larger buckets and reduces unnecessary stack traversals.
Instead of processing a single digit at a time, the algorithm tracks two active buckets:
upper
bottom
Values belonging to either bucket are pushed to stack B.
All other values are rotated.
Additional optimizations:
- Smart rotations
- Combined rotations (
rr) - Dynamic bucket progression
Elements are returned from B to A.
The algorithm continuously selects the largest remaining value.
A cost analysis determines whether:
rb
or
rrb
produces fewer operations.
Adjacent values may be repaired with:
sa
to avoid extra rotations.
Let:
base = √n
Number of digit groups:
log_base(n)
Since:
base = √n
then:
log_{√n}(n) = 2
which remains bounded.
Each element participates in a limited number of passes and stack operations.
The total number of generated Push_swap operations grows proportionally to:
n log n
Therefore the algorithm satisfies the required:
O(n log n)
complexity class.
Handles every permutation of 3 values using the minimum possible operations.
Operations used:
sa
ra
rra
For 4–5 values:
- Push smallest values to B.
- Sort remaining three values.
- Restore values from B.
This significantly reduces operation count for small inputs.
Implemented by:
display_bench()The benchmark tracks:
sa
sb
ss
pa
pb
ra
rb
rr
rra
rrb
rrr
and prints:
Disorder percentage
Strategy used
Complexity class
Total operations
Per-operation statistics
This feature is required by the project specification.
The repository includes:
checkerFeatures:
- Reads instructions from stdin
- Executes every operation
- Validates the final state
Output:
OK
if:
- Stack A is sorted
- Stack B is empty
Otherwise:
KO
Invalid instructions produce:
Error
| Strategy | Algorithm | Complexity |
|---|---|---|
| Simple | Selection-style extraction | O(n²) |
| Medium | √n partitioning | O(n√n) |
| Complex | Optimized Radix Sort | O(n log n) |
| Adaptive | Disorder-based selection | O(n²), O(n√n) or O(n log n) |
Artificial Intelligence tools were used only as learning and documentation aids.
AI assistance was limited to:
- Reviewing README structure
- Improving technical explanations
- Refining complexity analysis descriptions
- Grammar and documentation improvements
All algorithms, implementations, data structures, benchmark logic, parsing logic, adaptive strategy, and sorting techniques were designed, implemented, tested, and understood by the project contributors.
- Introduction to Algorithms — Cormen, Leiserson, Rivest, Stein
- The Art of Computer Programming — Donald Knuth
- Algorithm Design Manual — Steven Skiena
- Peer evaluations and project discussions within the 42 community