push_swap

push_swap is a 42 project written in C focused on sorting a stack using a limited set of operations.
The program takes a list of integers as input and prints the sequence of instructions required to sort them in ascending order, with the smallest number at the top of stack a.

The main challenge of the project is not only to sort correctly, but to do so with as few operations as possible.

Overview

This implementation combines different strategies depending on the input size:

• dedicated sorting logic for very small cases (2, 3, and 5 numbers)
• an indexing step to normalize values
• a K-sort / chunk-based approach for larger stacks

The project also includes input validation, duplicate detection, error handling, and a modular organization of stack operations and sorting logic.

Allowed Operations

The program is restricted to the operations defined in the subject:

• sa / sb / ss — swap the first two elements
• pa / pb — push from one stack to the other
• ra / rb / rr — rotate upwards
• rra / rrb / rrr — reverse rotate

The output consists exclusively of these instructions, one per line.

Algorithm Approach

Small inputs

For very small stacks, the program uses dedicated hardcoded strategies:

• 2 elements → simple swap if needed
• 3 elements → minimal-case sorting
• 4 or 5 elements → push the smallest values to stack b, sort the remaining stack, then push back

Large inputs

For bigger stacks, the program first indexes all values so that the smallest value becomes 0, the next becomes 1, and so on.
This simplifies comparisons and makes the sorting logic independent of the original numeric range.

After indexing, the program applies a K-sort inspired strategy:

1. push values from stack a to stack b according to a dynamic range
2. rotate b when appropriate to keep values positioned efficiently
3. move values back to a in descending index order

This approach gives solid results for larger inputs such as 100 or 500 numbers.

Project Structure

.
├── include/
│   └── push_swap.h
├── libft/
├── src/
│   ├── main.c
│   ├── operations/
│   │   ├── operations_core.c
│   │   ├── operations_swap_push.c
│   │   ├── operations_rotate.c
│   │   └── operations_reverse_rotate.c
│   ├── parsing/
│   │   ├── parsing.c
│   │   └── validation.c
│   ├── sort/
│   │   ├── small_sort.c
│   │   ├── big_sort.c
│   │   ├── sort_utils.c
│   │   ├── indexing.c
│   │   └── k_sort.c
│   └── utils/
│       ├── memory_utils.c
│       └── debug.c
└── Makefile

Compilation

Compile the project with:

make

Available Makefile rules:

make
make clean
make fclean
make re

Usage

Basic example:

./push_swap 4 63 455 -35 1 9

Arguments can also be passed as quoted strings:

./push_swap "2 1 3" 6 5 8

If the input is valid, the program prints the sequence of sorting instructions. If the input is invalid, the program prints:

Error

If the input is already sorted, the program produces no output.

Validation

This project handles:

• invalid numeric input
• duplicates
• integer overflow
• already sorted input
• multiple argument formats The program was tested with the official checker and additional manual cases.

What I Learned

Through this project, I improved my understanding of:

• stack-based problem solving
• linked list manipulation in C
• input parsing and validation
• algorithm design under strict constraints
• optimizing operations rather than only focusing on correctness
• organizing a C project into modular components

Notes

This project was developed as part of the 42 curriculum and reflects my approach to combining correctness, efficiency, and clean project structure in C.

License

This project is licensed under the MIT License. See the LICENSE file for details.