This project has been created as part of the 42 curriculum by nstreet-.

push_swap

Description

push_swap is a 42 sorting project focused on algorithmic thinking, stack manipulation, and move optimization. The program receives a list of integers as command-line arguments and prints a sequence of valid push_swap operations that sorts the numbers in ascending order using two stacks, a and b.

This implementation uses:

• input validation for invalid numbers, duplicates, empty arguments, and integer overflow
• dedicated routines for very small inputs (2, 3, and 5 numbers)
• rank assignment to normalize comparisons
• a two-phase strategy for larger inputs:
  • push elements from stack a to stack b using a dynamic range
  • bring elements back to stack a with the cheapest rotation cost, combining rotations when possible

The data structure is a doubly linked list-based stack, which makes push and rotation operations straightforward to express.

Features

• Validates every argument before sorting
• Prints Error to standard error on invalid input
• Exits silently when no sorting is needed
• Handles already sorted input without printing unnecessary operations
• Uses optimized paths for small stacks and a Turk-style heuristic for larger ones

Instructions

Compile

make

This builds the executable push_swap.

Available Make targets

make
make clean
make fclean
make re

Run

./push_swap 2 1 3 6 5 8

Example output:

sa
pb
pb
pb
sa
pa
pa
pa

The exact sequence may vary depending on the strategy used, but it must sort the input using only the allowed operations.

Input rules

• Arguments must be valid int values
• Duplicate numbers are rejected
• Non-numeric input is rejected
• On invalid input, the program writes Error to standard error

Examples:

./push_swap 3 2 1
./push_swap -5 10 0 42
./push_swap 1 2 2
./push_swap hello 3 4

Algorithm Overview

Small inputs

• 2 numbers: swap if needed
• 3 numbers: sort with a minimal case-based routine
• 4 or 5 numbers: push the smallest values to stack b, sort the remaining 3, then push back

Large inputs: Turk-style strategy with a sliding window

For larger stacks, this implementation follows a Turk-style approach split into two phases.

1. Rank normalization

Before any large sort starts, each value receives a rank based on how many values are smaller than it.
This transforms the problem from comparing raw integers to comparing positions in sorted order:

• the smallest value gets rank 0
• the largest value gets rank n - 1

This makes the algorithm independent of the original numeric range and simplifies placement decisions.

2. Phase one: push to b with a sliding window

The first phase moves values from stack a to stack b, but not in a naive order.
Instead, it uses a sliding window over the ranks:

• for inputs up to 100 numbers, the window size is 15
• for larger inputs, the window size is 33

The algorithm keeps a moving index i representing the next expected low rank.

At each step:

• if the top of a has a rank <= i, it is pushed to b and b is rotated immediately
• if the top of a has a rank <= i + range, it is pushed to b without rotating b
• otherwise, a is rotated until a suitable element appears at the top

This works like a sliding window because the accepted rank interval keeps moving forward as elements are pushed.
Lower ranks are sent deeper into b, while more recent values stay closer to the top. That distribution makes the second phase cheaper.

3. Phase two: cheapest reinsertion into a

Once every value is in b, the program rebuilds the sorted stack in a.

For each candidate node in b, it computes:

• the position of that node in b
• the target position where it should be inserted in a
• the number of rotations needed in both stacks

Those raw positions are converted into signed step counts:

• positive values mean rotate upwards (ra / rb)
• negative values mean reverse rotate (rra / rrb)

If both stacks need to move in the same direction, the algorithm can combine part of the work with:

• rr when both need upward rotations
• rrr when both need reverse rotations

So the move cost is:

• the larger of the two counts when directions match
• the sum of both counts when directions differ

The cheapest candidate is selected, executed, and pushed back to a with pa.

4. Final alignment

After all values return to a, the stack is almost sorted but may be rotated.
The final step rotates a until the minimum value is at the top, producing a fully sorted stack from top to bottom.

This keeps the implementation simple while reducing the total number of operations compared with a naive strategy.

Project Structure

includes/
  push_swap.h
src/
  main.c
  parsing.c
  stack.c
  ops_swap.c
  ops_push.c
  ops_rotate.c
  ops_rev_rotate.c
  sorting_small.c
  sorting_large.c
  turk_phase_1.c
  turk_phase_2.c
makefile

Resources

Project and topic references

• 42 push_swap subject PDF
• Notes on linked lists and stack operations for implementing rotations and pushes safely
• https://pure-forest.medium.com/push-swap-turk-algorithm-explained-in-6-steps-4c6650a458c0
• https://github.com/alx-sch/push_swap
• https://medium.com/@ayogun/push-swap-c1f5d2d41e97