push_swap

This project implements an algorithm to sort a list of numbers using two stacks (A and B) with a limited set of operations. The goal is to sort the numbers in stack A using the fewest possible moves.

Project Structure

File Description
push_swap.c Contains the main function that controls program flow.
push_swap.h Header file with function prototypes and shared declarations.
init_stack.c Initializes stacks A and B with input numbers.
sort_up_to_five.c Implements the sorting algorithm for stacks with up to 5 numbers.
sort_large.c Implements the sorting algorithm for stacks with more than 5 numbers.
operations.c Contains basic operations like swap, push, rotate, and reverse rotate.

Basic Instructions

Instruction Description
sa Swaps the top two elements of stack A.
sb Swaps the top two elements of stack B.
ss Executes sa and sb simultaneously.
pa Takes the top element from stack B and puts it on top of stack A.
pb Takes the top element from stack A and puts it on top of stack B.
ra Rotates all elements of stack A one position upward.
rb Rotates all elements of stack B one position upward.
rr Executes ra and rb simultaneously.
rra Rotates all elements of stack A one position downward.
rrb Rotates all elements of stack B one position downward.
rrr Executes rra and rrb simultaneously.

Sorting Algorithm

The algorithm consists of three main phases:

Phase 1: Move numbers from A to B

  1. Initial preparation:
    • Push the first two numbers from A to B without any calculations.
  2. Movement criteria:
    • Each number in A needs a “target node” in B - the smallest number in B that’s larger than the current number.
    • If no larger number exists in B, the target becomes the largest number in B.
  3. Cost calculation:
    • For each number in A, calculate operations needed to bring it to A’s top and its target to B’s top.
  4. Select cheapest node:
    • Find the number in A with the lowest push cost and move it to B.
  5. Repeat:
    • Continue until only three numbers remain in A.

Phase 2: Sort the remaining three numbers in A

  1. Three-number algorithm:
    • If numbers aren’t in ascending order:
      • Find the largest number and rotate it to the bottom.
      • Swap the top two if needed for proper order.

Phase 3: Move numbers from B to A

  1. Target node preparation:
    • Each number in B needs a “target node” in A - the largest number in A smaller than the current number.
    • If no smaller number exists, the target becomes A’s smallest number.
  2. Cost calculation:
    • Calculate operations needed to bring each number to B’s top and its target to A’s top.
  3. Select cheapest node:
    • Move the number with lowest push cost from B to A.
  4. Repeat:
    • Continue until B is empty.

Final Phase: Position smallest number in A

  • After all numbers are in A, find the smallest number.
  • If not at top, use rotations (ra/rra) to position it correctly.

Execution Example

Initial Stack A:

./push_swap 2 7 5 4 3 6 1

A   B   (TOP)
2
7
5
4
3
6
1

Phase 1: Move numbers from A to B

  1. Move first number (2) from A to B:
    • Number 2 moves directly to B.
A   B
7  [2]
5
4
3
6
1
  1. Move next number (7) from A to B:
    • Number 7 moves directly to B.
A   B
5  [7]
4   2
3
6
1
  1. Continue until only three numbers remain in A.

Phase 2: Sort remaining three numbers in A

  1. Three-number algorithm:
    • Sort the final three numbers in A.
A   B
1   4
3   2
6   7
     5

Phase 3: Move numbers from B to A

  1. Move numbers back to A using minimum cost algorithm.

Final Phase: Position smallest number

  • Adjust so smallest number (1) is at top.
A   B
1
2
3
4
5
6
7

Optimization Tips

  1. Combine rotations: When possible, use rr/rrr instead of separate ra/rb or rra/rrb
  2. Pre-calculate moves: Determine optimal paths before executing operations
  3. Edge cases: Special handling for nearly-sorted or small stacks (<6 elements)
  4. Visualization: Use print functions during development to track stack states

References