Push Swap

A sorting algorithm implementation using only two stacks and a limited set of operations. This project is part of the 42 School curriculum and focuses on algorithmic efficiency and optimization.

Table of Contents

• About
• Algorithm: The Turk Approach
• Project Structure
• Compilation & Usage
• Implementation Details
• What I Learned
• Challenges Faced
• Performance

About

Push_swap is a sorting algorithm project that challenges you to sort data using two stacks (A and B) with a minimal number of operations. The goal is to sort integers in stack A in ascending order using only the following operations:

Operation	Description
sa	Swap the first two elements at the top of stack A
sb	Swap the first two elements at the top of stack B
ss	sa and sb at the same time
pa	Push the first element of stack B to stack A
pb	Push the first element of stack A to stack B
ra	Rotate stack A (shift up all elements by 1)
rb	Rotate stack B (shift up all elements by 1)
rr	ra and rb at the same time
rra	Reverse rotate stack A (shift down all elements by 1)
rrb	Reverse rotate stack B (shift down all elements by 1)
rrr	rra and rrb at the same time

Algorithm: The Turk Approach

I implemented the Turk Algorithm, a cost-based optimization strategy that minimizes the number of moves required to sort the stack.

Core Concept

The algorithm works by:

1. Initial Setup: Push all elements except 3 to stack B (or handle special cases for 2-5 elements)
2. Base Case: Sort the remaining 3 elements in stack A using sort_three()
3. Cost Analysis: For each element in stack B, calculate the "cost" to push it back to its correct position in stack A
4. Optimal Moves: Repeatedly move the "cheapest" element (lowest cost) from B to A
5. Final Rotation: Rotate stack A to place the smallest element at the top

Cost Calculation

For each element in stack B, the algorithm calculates:

• Position cost in B: How many rotations to bring it to the top
• Target cost in A: How many rotations to position its target node at the top
• Total cost: Sum of both costs, considering optimization for double rotations (rr/rrr)

The element with the lowest total cost is moved first.

Target Node Selection

For each element in B, the algorithm finds its "target" in stack A:

• The target is the smallest element in A that is still larger than the current B element
• If no such element exists, the target is the smallest element in A

This ensures elements are inserted in the correct sorted position.

Project Structure

.
├── push_swap.h          # Main header with struct and function declarations
├── main.c               # Entry point and sorting dispatcher
├── turk.c               # Main Turk algorithm logic
├── turk1.c              # Node initialization and cost calculation
├── sort_three.c         # Special cases (2-3 elements) and utilities
├── stack_init.c         # Stack creation and initialization
├── stack_utils.c        # Stack manipulation utilities
├── errors.c             # Input validation and error handling
├── split.c              # String splitting for single-argument input
├── push.c               # Push operations (pa, pb)
├── swap.c               # Swap operations (sa, sb, ss)
├── rotate.c             # Rotate operations (ra, rb, rr)
├── rev_rotate.c         # Reverse rotate operations (rra, rrb, rrr)
└── Makefile             # Compilation rules

Compilation & Usage

Build

make

This creates the push_swap executable.

Run

# Single argument (space-separated)
./push_swap "3 2 1 5 4"

# Multiple arguments
./push_swap 3 2 1 5 4

# With negative numbers
./push_swap -5 2 0 -1 8

Clean

make clean   # Remove object files
make fclean  # Remove object files and executable
make re      # Rebuild from scratch

Implementation Details

Data Structure

typedef struct s_element
{
    int                 value;              // Integer value
    int                 current_position;   // Index in stack
    int                 push_price;         // Move cost
    bool                above_median;       // Position flag for optimization
    bool                cheapest;           // Flag for cheapest element
    struct s_element    *target_node;       // Target position in other stack
    struct s_element    *next;              // Next element
    struct s_element    *prev;              // Previous element
}   t_element;

This circular doubly-linked list structure allows efficient rotation operations and bi-directional traversal.

Key Functions

turk1.c:

• update_node_positions(): Updates indices and median flags
• find_target_nodes(): Identifies optimal insertion points
• calculate_move_costs(): Computes push costs for all elements
• find_cheapest_move(): Selects the minimum-cost element

turk.c:

• move_nodes(): Executes the optimal move sequence
• sort_stack(): Main sorting loop implementing the Turk algorithm
• finish_rotation(): Brings target element to top efficiently

sort_three.c:

• sort_three(): Hardcoded optimal solution for 3 elements (max 2 moves)
• handle_five(): Special optimization for 5 elements

Edge Cases Handled

• Empty input
• Single element
• Already sorted stack
• Reverse sorted stack
• Duplicates (error)
• Non-numeric input (error)
• Integer overflow (INT_MIN/INT_MAX edge case)

What I Learned

Algorithm Design

• Cost-based optimization: Understanding how to evaluate and compare different move sequences
• Greedy approaches: Making locally optimal choices that lead to global optimization
• Target selection: Finding the right insertion point using comparative logic

Data Structures

• Circular doubly-linked lists: Efficient for rotation operations without array copying
• Metadata storage: Using struct fields to cache computed values (position, cost, flags)

Performance Optimization

• Double rotation detection: Using rr/rrr when both stacks need rotation in the same direction
• Median-based optimization: Choosing between rotate and reverse rotate based on position
• Special case handling: Optimized paths for small inputs (2, 3, 5 elements)

C Programming

• Memory management: Proper allocation/deallocation of dynamic linked lists
• Pointer manipulation: Navigating and modifying complex linked structures
• Input parsing: Handling various input formats (single string vs multiple args)
• Error handling: Validating input and preventing memory leaks on errors

Problem-Solving

• Complexity analysis: Understanding O(n²) behavior and accepting it for this problem size
• Trade-offs: Balancing code simplicity vs. move count optimization
• Debugging strategies: Visualizing stack states and operation sequences

Challenges Faced

1. Understanding the Turk Algorithm

Initially, I struggled to grasp how the cost calculation worked, especially with double rotations. Breaking it down into separate functions (calculate_move_costs, find_target_nodes) helped me understand each component.

2. Edge Case: INT_MIN and INT_MAX Together

When both INT_MIN and INT_MAX appear in a 2-element stack, standard comparison logic breaks due to integer overflow. I added a special check in main.c:20-27 to handle this case.

3. Memory Leaks on Error

Ensuring all allocated memory was freed when errors occurred (especially with the split input) required careful tracking of the is_split flag and proper cleanup in error paths.

4. Circular List Navigation

Implementing circular doubly-linked lists was tricky at first. I had to carefully maintain next/prev pointers during push/pop operations to avoid segfaults.

5. Optimizing for Small Inputs

Finding the optimal hardcoded solutions for 2 and 3 elements required drawing out all possible permutations and their minimal move sequences.

6. Double Rotation Logic

Detecting when both stacks need rotation in the same direction (to use rr or rrr instead of separate ra/rb) was complex. The key insight was checking if both nodes are above/below median.

Performance

The implementation achieves the following approximate move counts:

Stack Size	Average Moves	42 School Requirement
3	≤ 2	≤ 3
5	≤ 12	≤ 12
100	~700	< 900 (5 pts), < 700 (4 pts)
500	~5500	< 7000 (5 pts), < 5500 (4 pts)

The Turk algorithm provides consistent O(n²) performance with good practical results for the required test sizes.

---

Author: sedto School: 42 Lausanne Date: February - March 2025