Push Swap

A sorting algorithm project from the 42 Common Core curriculum that implements a Radix Sort to sort a stack of integers using a limited set of operations.

Project Overview

Push Swap is a problem that requires sorting a stack of integers using two stacks (A and B) and a restricted set of operations. The challenge is to sort the data using the minimum number of moves possible.

Stack Operations

The program supports the following operations:

• sa / sb - Swap the first two elements of stack A / B
• ss - Swap the first two elements of both stacks
• pa / pb - Push the first element of stack B / A to stack A / B
• ra / rb - Rotate stack A / B upward (first element goes to the end)
• rra / rrb - Reverse rotate stack A / B downward (last element goes to the top)
• rr / rrr - Rotate / Reverse rotate both stacks simultaneously

Algorithm: Radix Sort with Binary Comparison

This implementation uses Radix Sort, a non-comparative sorting algorithm that works by distributing elements into buckets based on their radix (digit value). In this case, the radix is binary (0 or 1).

Key Concept: Number Ranking

Before sorting, all input numbers are assigned a rank (0 to n-1) based on their position in ascending order. This ranking has two important benefits:

1. Handles negative numbers - Ranks are unsigned integers, eliminating issues with negative number comparisons
2. Binary representation - Ranks provide a clean binary representation for bit-by-bit comparison

How Binary Radix Sort Works

1. Extract bits progressively - Starting from the least significant bit (LSB) and moving to the most significant bit (MSB)
2. Two-bucket distribution - For each bit position:
   • Elements with bit value 0 → Move to stack B
   • Elements with bit value 1 → Stay in stack A
3. Reintegrate - Move all elements from stack B back to stack A
4. Repeat - Continue for each bit position until the stack is sorted

Example with binary representation:

Original numbers:  [3, 1, 2]
Ranks assigned:    [2, 0, 1]  (0=smallest, 1=middle, 2=largest)

Binary representation of ranks:
  2 = 10 (binary)
  0 = 00 (binary)
  1 = 01 (binary)

Bit 0 (rightmost):   Process bits [0, 0, 1]
Bit 1 (next):        Process bits [1, 0, 0]

After passes, ranks are sorted: [0, 1, 2]
Which corresponds to sorted original: [1, 2, 3]

Special Handling for Small Stacks

For efficiency, stacks with 2-5 elements are sorted using optimized hardcoded routines:

• 2 elements - Single swap if needed
• 3 elements - 2-move maximum sort
• 4-5 elements - Move minimum elements to stack B, sort remainder, then reinsert

Project Structure

push_swap/
├── includes/
│   └── push_swap.h          # Main header with struct definitions
├── src/
│   ├── main.c               # Entry point and initialization
│   ├── push_swap.c          # Core radix sort algorithm
│   ├── ranks.c              # Ranking system implementation
│   ├── algorithm_utils.c    # Helper functions for sorting
│   ├── stack_manager.c      # Stack creation and management
│   ├── stack_moves.c        # Stack operation implementations
│   ├── push_swap_utils.c    # Utility functions
│   ├── arg_check.c          # Input validation
│   └── init.c               # Initialization functions
├── libft/                   # Custom C library
├── Makefile                 # Build configuration
└── README.md                # This file

Stack Structure

typedef struct s_stack
{
    int             number;   // Original number
    unsigned int    rank;     // Ascending order position (0 to n-1)
    struct s_stack  *next;    // Pointer to next node
} t_stack;

Compilation and Usage

Build

make              # Compile the project
make clean        # Remove object files
make fclean       # Remove all generated files
make re           # Clean and rebuild

Run

./push_swap <numbers>

Examples:

./push_swap 3 2 1
# Output: pb ra pa

./push_swap 2 1
# Output: sa

./push_swap 4 3 2 1 0
# Output: pb pb pb pa pa

Test with Validation

# Generate random numbers and verify the output
./push_swap $(python3 -c "import random; print(' '.join(map(str, random.sample(range(-1000, 1000), 100))))") | wc -l

Complexity Analysis

• Time Complexity: O(n * log₂(max_rank)) = O(n * log n) where max_rank ≈ n
• Space Complexity: O(n) for storing the two stacks

Learning Resources

This implementation was greatly inspired by the comprehensive guide on Radix Sort:

• Push Swap Tutorial - Medium

This guide provides excellent visualizations and explanations of how radix sort can be applied to the push swap problem using binary representations.

Author

vjan-nie - 42 Madrid Student

---

Note: This is a 42 Common Core project. The implementation focuses on understanding sorting algorithms, memory management in C, and algorithmic optimization.