This project has been created as part of the 42 curriculum by csekakul and rafsanch.

Push_swap: Complexity Analysis Under Stack Constraints 📊

Welcome to push_swap, a C programming project focused on sorting data on a constrained stack architecture using the lowest possible number of operations.

🚀 Project Overview

The objective is to calculate and output the most optimized sequence of stack manipulation operations to sort a random stack of unique integers. The program computes a real-time disorder metric from the raw input and dynamically shifts sorting routes across four distinct algorithmic regimes to preserve performance.

📂 Project Structure

File Mapping Component	Architectural Assignment Profile
📄 Makefile	Multi-rule compilation automation script (all, clean, fclean, re, bonus).
📄 push_swap.h	Global definitions layout, configuration structures, and standard system includes.
📄 main.c	Program entry pipeline managing CLI string configuration routing.
📄 strategy.c	Strategy evaluation matrix choosing matching algorithmic regimes at runtime.
📄 indexing.c	Coordinate item normalization system mapping variable arrays to relative indices.
📄 bench.c	Instruction metric logger processing profiling analytics maps over stderr.
📄 parsing.c	System input sanitation, type compliance checking, and overflow guards.
📄 split.c	Substring boundary tokenizer isolating multi-element execution arrays.
📄 stack.c	Stack array buffer instantiations and tracking boundary conditions.
📄 io_helpers.c	Low-level streaming pipelines routing structural string feedback characters.
📄 push.c	Emulated push instructions execution engine (pa, pb).
📄 swap.c	Emulated internal array element flipping subroutines (sa, sb, ss).
📄 rotate.c	Shift-up circular index tracking operations block (ra, rb, rr).
📄 reverse_rotate.c	Shift-down circular index tracking operations block (rra, rrb, rrr).
📄 sort_small.c	Hardcoded structural optimization paths resolving constraints for $\le 3$ elements.
📄 sort_helpers.c	Relative threshold utilities tracking minimum targets for groups under 5 elements.
📄 simple_sort.c	Baseline selection insertion strategy handling the $O(n^2)$ baseline regime.
📄 medium_sort.c	Block partitioning range-based handler driving the $O(n\sqrt{n})$ regime.
📄 complex_sort.c	Bitwise Radix LSB transformation handler executing the $O(n \log n)$ regime.
📄 k_sort.c	High-efficiency range chunking module optimized for low-disorder tracking.
📄 adaptive_sort.c	Mathematical pairwise inversion metric loop mapping input chaos directly.
📄 utils.c	Isolated utility algorithms and secondary standard performance functions.

Description

The program takes a list of integers as arguments and outputs a sequence of operations that sorts the numbers in ascending order using two stacks (A and B) and a limited set of operations.

At this stage, the program supports:

• Parsing and Validation

  • Accepts integers from command line arguments
  • Handles multiple numbers per argument
  • Validates input: only integers, no duplicates
  • Converts strings to integers and stores them in stack A

• Stack Operations

  • Swap operations: sa, sb, ss
  • Push operations: pa, pb
  • Rotate operations: ra, rb, rr
  • Reverse rotate operations: rra, rrb, rrr

1. Simple Algorithm — O(n²)

Implemented in: simple_sort

Approach:

• Repeatedly push the smallest element from stack A to B
• Sort the remaining small subset (≤5 elements)
• Push elements back to A

Characteristics:

• Deterministic and easy to implement
• Efficient for small inputs
• Not suitable for large datasets

---

2. Medium Algorithm — O(n√n)

Implemented in: chunk_sort

Approach:

• Divide the indexed values into chunks
• Push elements from A to B based on chunk ranges
• Use rotations (rb) to position smaller elements deeper in B
• Reconstruct A by pushing back the largest elements first

Key Idea:

• Reduces unnecessary movements by grouping values

Tuning:

• Chunk size is proportional to input size (e.g., n / 5)
• Proper tuning significantly improves performance

Performance:

• Designed to achieve <700 operations for 100 numbers (excellent target)

---

3. Complex Algorithm — O(n log n)

Implemented in: radix_sort

Approach:

• Uses binary radix sort
• First normalizes values using indexing
• Sorts numbers bit by bit using pb and ra
• Rebuilds stack A after each bit pass

Characteristics:

• Very stable and predictable
• Guarantees good performance for large inputs
• Not optimal for small or partially sorted datasets

---

4. Adaptive Algorithm — Hybrid Strategy

Implemented in: adaptive_sort

Disorder Metric

Before sorting, the program computes a disorder value (0 → 1):

• 0: already sorted
• 1: completely reversed
• Based on pairwise inversions

---

Strategy Selection

Disorder Range	Strategy Used	Complexity
< 0.2	Simple / near-sorted handling	~O(n)
< 0.5	Chunk sort	O(n√n)
≥ 0.5	Radix sort	O(n log n)

Rationale:

• Low disorder: minimal fixes required → avoid heavy algorithms
• Medium disorder: chunking balances efficiency and control
• High disorder: radix guarantees consistent performance

---

Small Stack Optimization (Critical)

Before applying any strategy, the program always handles small inputs:

• 2–3 elements: optimal hardcoded logic (sort_small)
• 4–5 elements: push smallest values to B, sort remaining, then restore

Example:

Input	Output
[3, 2, 1]	sa rra

This guarantees minimal operations and avoids unnecessary use of complex algorithms.

---

Strategy Selection

The program supports runtime selection:

./push_swap [strategy] numbers...

---

Algorithm Selection and Justification

Small Stack Sorting (2–5 numbers)

1. 2–3 numbers:

   • Simple comparison logic using sa, ra, rra to sort 2 or 3 numbers

2. 4–5 numbers:

   • Find the smallest (or two smallest) numbers in stack A
   • Rotate stack A to bring the smallest to the top
   • Push smallest number(s) to stack B (pb)
   • Sort the remaining 3 numbers in stack A
   • Push numbers back from stack B to stack A (pa)
   • Rotations are chosen to minimize the number of moves

Justification:

• This approach is deterministic and optimal for very small stacks, ensuring minimal operations
• It is scalable, as the same push/pop strategy can be extended for larger sorting algorithms later (radix sort, etc.)
• Keeps code modular and reusable, separating operations from parsing and sorting logic

Examples:

Input Stack	Output Operations
[2, 1, 3]	sa
[3, 2, 1]	sa rra
[2, 3, 1]	rra
[1, 3, 2]	sa ra

• These sequences ensure the stack is sorted in ascending order with minimal moves.

---

3. Use of Two Stacks (A and B)

• Even though sorting ≤3 numbers does not require stack B, the project architecture uses two stacks in preparation for sorting larger inputs.
• All operations (push, swap, rotate, reverse rotate) are implemented for both stacks to allow scalability.

Design Choices

• Array-based stacks for simplicity and performance
• Indexing system to normalize values for radix and chunk algorithms
• Modular structure:
  • Parsing
  • Operations
  • Strategies
• Adaptive approach to handle different input patterns efficiently

rafsanch Contributions

• Designed the initial project structure
• Implemented:
  • Argument parsing and validation
  • Stack structure using arrays
  • Core stack operations (sa, pb, ra, etc.)
  • Simple sorting algorithm (O(n²))
• Developed:
  • Memory handling and error management
  • Improvements in ft_split (fixing edge cases and leaks)
• Added:
  • K sort algorithm for low-disorder optimization
  • Safer operation execution (avoiding invalid instruction outputs)
• Performed:
  • Final integration
  • Debugging (memory leaks, edge cases)
  • Norminette compliance and testing

---

csekakul Contributions

• Researched and implemented advanced sorting strategies:
  • Radix sort (complex strategy)
  • Chunk sort (medium strategy)
  • Adaptive sorting system
• Developed:
  • Indexing system (indexing.c) for normalization
  • Disorder computation logic
  • Strategy selection system (strategy.c)
• Implemented:
  • Benchmarking system (bench.c)
  • Supporting I/O utilities (io_helpers.c)
• Contributed to:
  • Small number sorting logic (≤5 elements)
  • Project documentation and README resources

---

Shared Contributions

• Algorithm design discussions and decisions
• Strategy selection (arrays vs linked lists)
• Testing and validation of sorting behavior
• Performance evaluation and optimization decisions
• Final project review and preparation for evaluation

---

Collaboration Highlights

• Clear communication and regular updates via chat
• Efficient division of responsibilities
• Strong combination of:
  • algorithmic design
  • systems implementation
• Flexible planning aligned with project deadlines

---

Instructions

Compile the program using Makefile:

make

Compile the program manually:

cc -Wall -Wextra -Werror *.c -o push_swap

Run

./push_swap 3 2 1

Run with specific strategy

./push_swap --medium 5 2 8 1 3

Resources

• Push Swap Visualizer
• Push Swap Explanation
• Inspiration
• Overview
• Jump/branch table
• Structures CS50 video
• Structs CS50 video
• Defining custom types CS50 video
• Struct Wikipedia

AI Assistance

During the development of this project, AI tools were used for:

• Clarifying concepts: understanding stack operations, parsing, and sorting logic.
• Planning: designing the step-by-step approach for small stack sorting.
• Debugging guidance: identifying compilation errors, type mismatches, and improving function structure.
• Writing README and documentation: creating clear explanations of algorithms and program structure.

Important Notes

• No AI-generated code was used to bypass learning objectives.
• All final implementations were written and tested manually.
• AI assistance was strictly used as a learning and planning aid, similar to consulting with peers or mentors.