push_swap

A sorting algorithm project developed as part of the curriculum at 42 Heilbronn. This program sorts a stack of integers using a limited set of operations, with the goal of minimizing the number of moves required.

Overview

The push_swap project challenges students to implement an efficient sorting algorithm using only two stacks and a restricted set of operations. The program must take a list of integers as input and output a series of operations that will sort the stack in ascending order with the smallest number at the top.

This project deepens understanding of algorithm complexity, data structures, and optimization techniques. Different sorting strategies are employed based on the input size, from hardcoded solutions for small sets to binary radix sort for larger inputs.

Project Structure

The program is organized into several categories of functions:

Stack Operations

The following operations can be performed on the stacks:

• sa - swap a: swaps the first two elements at the top of stack a
• sb - swap b: swaps the first two elements at the top of stack b
• ss - swap both: performs sa and sb simultaneously
• pa - push a: takes the top element from stack b and puts it on top of stack a
• pb - push b: takes the top element from stack a and puts it on top of stack b
• ra - rotate a: shifts all elements of stack a up by one (first becomes last)
• rb - rotate b: shifts all elements of stack b up by one
• rr - rotate both: performs ra and rb simultaneously
• rra - reverse rotate a: shifts all elements of stack a down by one (last becomes first)
• rrb - reverse rotate b: shifts all elements of stack b down by one
• rrr - reverse rotate both: performs rra and rrb simultaneously

Input Parsing

Functions for validating and parsing input:

• parse_input - converts command line arguments to integer array
• Validates for duplicates and non-numeric input
• Handles both space-separated and individual arguments
• Error checking for integer overflow

Sorting Algorithms

The program uses different sorting strategies based on input size:

Small Sorts (2-5 elements)

• sort_two - swaps two elements if needed
• sort_three - hardcoded optimal solution for 3 elements
• sort_small - sorts 4-5 elements by isolating minimum values

Binary Radix Sort (6+ elements)

• binary_radix_sort - efficient sorting using binary representation
• Processes numbers bit by bit from least to most significant
• Uses both stacks to partition numbers based on bit values
• Optimal for larger datasets with O(n * log n) complexity

Helper Functions

Utility functions supporting the sorting operations:

• index_array - converts values to their sorted indices
• is_sorted - checks if stack is already sorted
• find_min_position - locates the minimum value in the stack
• bubble_sort - helper for creating sorted reference array
• init_stacks - initializes stack data structures
• fill_stack - populates stack with parsed values

Compilation

The program uses a Makefile with the following targets:

make        # Compiles the program
make clean  # Removes object files
make fclean # Removes object files and the executable
make re     # Recompiles the entire program

The compilation produces an executable file push_swap that can be run with integer arguments.

Usage

To use the program:

1. Clone the repository and compile:

git clone https://github.com/Lizard31/push_swap.git
cd push_swap
make

2. Run the program with a list of integers:

./push_swap 3 2 1

The program will output the operations needed to sort the stack:

sa
rra

Usage Examples

Sort three numbers:

./push_swap 2 1 3

Sort with space-separated arguments:

./push_swap "4 67 3 87 23"

Sort a larger set:

./push_swap 5 8 2 9 1 7 3 6 4

Checking the Result

You can verify that the operations correctly sort the stack by using a checker program. The checker is typically provided separately as part of the 42 project resources:

ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker $ARG

Note: The checker program must be obtained separately and is not included in this repository.

Algorithm Strategy

The push_swap implementation uses different strategies based on input size:

For 2 elements:

Simply swap if they are in the wrong order.

For 3 elements:

Use hardcoded comparisons to determine the optimal sequence of moves (maximum 2 operations).

For 4-5 elements:

Push the smallest values to stack b, sort the remaining 3 elements, then push back from stack b.

For 6+ elements:

Implement binary radix sort:

1. Convert all numbers to their indices in the sorted array (0 to n-1)
2. For each bit position (from least to most significant):
   • Push numbers with 0 at current bit position to stack b
   • Rotate numbers with 1 at current bit position in stack a
   • Push all numbers back from stack b to stack a
3. Repeat until all bits are processed

This approach guarantees efficient sorting with a predictable number of operations.

Technical Details

• All code follows the 42 Norm coding standards
• The program is written in C and compiles with -Wall -Wextra -Werror flags
• Memory management is handled carefully to prevent leaks
• Error handling outputs "Error\n" to stderr for invalid input
• The program handles edge cases including:
  • Already sorted input (no operations needed)
  • Duplicate values (error)
  • Non-numeric input (error)
  • Integer overflow (error)
  • Empty input (no output, clean exit)