This project has been created as part of the 42 curriculum by acamelo and criredon.

push_swap 🔄 — Adaptive Algorithmic Sorting Engine

1. General Description & Project Objectives

push_swap is an algorithmic C program designed to sort a list of integers using two stacks (a and b) and a restricted instruction set: sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, and rrr. The program does not print the sorted numbers directly; instead, it outputs the precise sequence of operations required to achieve order.

The core teaching objective is to master algorithmic complexity—understanding how the number of operations scales relative to input size ($N$).

The project is built upon four fundamental pillars: Stacks (restricted position manipulation), Disorder Index (metrics for dynamic strategy selection), Big-O Complexity (scalability analysis), and Advanced Sorting Algorithms (minimum extraction, chunk partitioning, and Radix Sort).

---

2. Instructions & Usage

2.1. Compilation and Execution

make
./push_swap 4 67 3 87 23
./push_swap --simple 4 67 3 87 23
./push_swap --medium 4 67 3 87 23
./push_swap --complex 4 67 3 87 23
./push_swap --adaptive 4 67 3 87 23

The Makefile includes standard targets (all, clean, fclean, re) and compiles strictly with: cc -Wall -Wextra -Werror.

2.2. Usage Examples & Testing

./push_swap 2 1
sa

Validation with the provided checker:

ARG="4 67 3 87 23"
./push_swap --complex $ARG | ./checker_linux $ARG
# Expected output: OK

Operation counting:

ARG="4 67 3 87 23"
./push_swap $ARG | wc -l

---

3. Resources & References

3.1. Classical References Consulted

• Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms: Chapters on "Growth of Functions" and "Sorting in Linear Time" (specifically Radix Sort).
• Kernighan and Ritchie, The C Programming Language: Chapters on "Pointers and Arrays" and "Structures", serving as the foundation for linked list node management.

3.2. Expert Repositories & Study Material

Consulted for reference, logic contrasting, and architectural benchmarking:

• YouTube - Push_swap algorithmic breakdown
• YouTube - Sorting strategy analysis
• YouTube - Radix implementation logic
• YouTube - Performance optimization review
• GitHub - hu8813 push_swap tester

3.3. AI Usage Statement

Artificial Intelligence was utilized as a conceptual learning assistant to clarify algorithmic complexities, review error edge cases, propose test vectors, and assist with structured technical documentation. All C code implementation and architecture were written manually.

---

4. Technical Decisions, Architecture & Data Structures

4.1. Architecture & Data Structures

The engine relies on a singly linked list. Each node stores its raw integer value, its normalized sorted index, and a pointer to the next node. This avoids redundant structures and accurately represents stack behavior. Input values are pre-processed into normalized indices ($0 \dots n-1$), allowing algorithms to operate on relative positions rather than raw values.

START
  |
  v
Parse flags and input arguments
  |
  v
Valid input? ---- no ----> Error (stderr)
  |
  yes
  v
Initialize Stack A
  |
  v
Assign normalized indices
  |
  v
Calculate disorder index
  |
  v
Select and execute strategy
  |
  +--> Simple
  +--> Medium
  +--> Complex
  +--> Adaptive
  |
  v
Execute and print operations
  |
  v
Free allocated memory
  |
  v
END

4.2. Core File Structure

• 0_main.c: Program entry point and central coordinator.
• 1_detect_flags.c: CLI flag parsing (--simple, --medium, --complex, --adaptive).
• 2_parse_numbers.c: Argument validation, split handling, duplicate detection, and overflow checks.
• 3_prepare_stack.c: Stack allocation, indexing, and memory deallocation.
• 4_calculate_disorder.c: Mathematical disorder ratio computation.
• 5_1_execute_strategy.c: Strategy router based on flags and metrics.
• 5_2_sort_simple.c: Minimum extraction sorting for small datasets.
• 5_3_sort_medium.c: Chunk-based sorting for medium datasets.
• 5_4_sort_complex.c: LSD Radix Sort engine for large datasets.
• 5_5_sort_adaptative.c: Heuristic adaptive sorting router.
• 6_*_operations_*.c: Atomic stack manipulation operations.

4.3. Theoretical Foundations

• Stack: LIFO data structure where access is restricted to the top node.
• Linked List: Nodes connected via pointers allowing dynamic reordering without data copying.
• Normalized Index: Relative rank of a value within the sorted dataset.
• Disorder Index: Ratio of inverted pairs to total pairs, computed prior to execution.
• Big-O Notation: Measures algorithm scalability relative to input size $N$.

The adaptive strategy uses thresholds defined in the project guidelines:

• Disorder $< 0.2$ → target $O(n)$
• $0.2 \le$ Disorder $< 0.5$ → target $O(n\sqrt{n})$
• Disorder $\ge 0.5$ → target $O(n \log n)$

---

4.4. Strategy & Algorithm Summary Table

Strategy	Selected Algorithm	Target Complexity	Core Concept
Simple	Minimum Extraction	$O(n^2)$	Locates minimum, moves it to top, and temporarily pushes to Stack B.
Intermediate	Chunk-based / Range Sorting	$O(n\sqrt{n})$	Divides index space into chunks of size $\approx \sqrt{N}$ and processes by groups.
Complex	LSD Radix Sort	$O(n \log n)$	Processes index bits iteratively using pb, ra, and pa.
Adaptive	Custom Adaptive Router	$O(n) / O(n\sqrt{n}) / O(n \log n)$	Evaluates disorder metrics to dynamically trigger Simple, Medium, or Complex sorting.

---

4.5. Risk Mitigation & Validation Tests

Edge cases verified prior to submission: empty arguments, single numbers, already sorted lists, negative numbers, INT_MIN, INT_MAX, duplicates, malformed strings, and overflow scenarios.

Functional check:

ARG="4 67 3 87 23"
./push_swap $ARG \vert{} ./checker_linux$ARG

Memory leak audit:

valgrind --leak-check=full ./push_swap 5 4 3 2 1

Performance benchmarks:

ARG="$(shuf -i 1-10000 -n 100)"
./push_swap $ARG | wc -l # Target: < 2000 ops

ARG="$(shuf -i 1-10000 -n 500)"
./push_swap $ARG | wc -l # Target: < 12000 ops

---

5. Conclusion

push_swap proves that producing correct code is insufficient; true engineering lies in scalability and efficiency. The primary takeaway is analyzing structural data constraints and selecting the optimal algorithmic architecture for each computational context.