This project has been created as part of the 42 curriculum by hrasamoe and nrasamis.

Description

Overview

push_swap sorts a stack of integers using two stacks (A and B) and a limited set of operations.

Goal: Sort stack A in ascending order using the fewest operations possible.

This implementation features an adaptive engine that evaluates input disorder and automatically selects the most efficient sorting strategy.

---

How It Works

You start with:

• Stack A — contains all integers (unsorted)
• Stack B — empty (auxiliary stack)

Allowed Operations

Operation	Description
sa	Swap top 2 elements of A
sb	Swap top 2 elements of B
ss	sa + sb
pa	Push top of B to A
pb	Push top of A to B
ra	Rotate A (top → bottom)
rb	Rotate B (top → bottom)
rr	ra + rb
rra	Reverse rotate A (bottom → top)
rrb	Reverse rotate B (bottom → top)
rrr	rra + rrb

The program prints each operation to stdout, one per line.

---

Instructions

Installation

git clone <repository_url>
cd push_swap
make

Makefile Commands

make clean
make fclean
make re

---

Usage

Basic

./push_swap 4 2 7 1 9 3

String Input

./push_swap "4 2 7 1 9 3"

Mixed Input

./push_swap "4 2 7" 1 9 3

---

Flags

Flag	Description
--bench	Print performance stats to stderr
--simple	Force selection sort
--medium	Force chunk sort
--complex	Force radix sort
--adaptive	Default automatic strategy

Example

./push_swap --complex --bench 4 2 7 1 9 3

---

Edge Cases

./push_swap 1 2 3 4 5   # Already sorted → no output
./push_swap 42          # Single element → no output
./push_swap -3 0 5 -1 2 # Supports negatives

Errors

./push_swap 1 2 a 3       # Invalid input
./push_swap 1 2 2 3       # Duplicate
./push_swap 99999999999   # Overflow

Prints Error to stderr

---

Resources

• https://www.geeksforgeeks.org/dsa/radix-sort/
• https://push.eliotlucas.ch/
• https://www.guru99.com/fr/bucket-sort.html

---

AI Usage

AI (Claude) was used for:

• Algorithm explanations
• Refactoring guidance
• Debugging memory issues
• Documentation writing

Algorithms

Adaptive Mode (default)

disorder < 0.2   → selection sort     O(n²)
disorder < 0.5   → chunk sort         O(n√n)
disorder ≥ 0.5   → radix sort         O(n × k)

---

1. Small Sort (Selection Sort)

• N ≤ 5 → optimized cases
• N > 5 → repeatedly push minimum to B

Concept:

Find min → push to B → repeat → push back to A

Complexity: O(n²)

---

2. Chunk Sort (Medium Lists)

Best for medium-sized inputs (~100 elements).

Steps:

1. Normalize values (assign ranks)
2. Divide into chunks (√N)
3. Push chunk by chunk to B
4. Rebuild A by pushing max from B

⏱ Complexity: O(n√n)

---

3. Radix Sort (Large Lists)

Best for large inputs.

Steps:

1. Normalize values (ranking)

2. Process bits from LSB to MSB:

   • bit = 0 → pb
   • bit = 1 → ra

3. Push back from B to A

Complexity: O(n × k) (k = number of bits)

---

Disorder Metric

Measures how shuffled the input is:

disorder = inversions / (N × (N - 1) / 2)

• 0.0 → sorted
• 1.0 → reverse sorted
• 0.5 → random

Complexity: O(n²)

---

Benchmark

./push_swap --bench $(cat args.txt)

Example output:

[bench] disorder: 0.62
[bench] strategy: radix_sort
[bench] total_ops: 4872

---

Checker

./push_swap $(cat args.txt) | ./checker_linux $(cat args.txt)

Count operations:

./push_swap $(cat args.txt) | wc -l

---

Contributions

Shared Work

• Debugging
• Testing (large datasets)
• Code review
• Checker integration

hrasamoe

• Algorithms (simple & complex)
• Parsing & validation
• Makefile
• Benchmark system

nrasamis

• Stack operations
• Medium algorithm & disorder metric
• Adaptive engine
• Header (push_swap.h)
• README

---