Skip to main content

​
Overview

This page demonstrates Push Swap behavior across different input sizes, from trivial cases to complex sorting scenarios.

​
Sorting 2 Numbers

The simplest non-trivial case uses a single swap operation.

​
Example: Two Unsorted Numbers

./push_swap 5 3
Output
sa
This triggers the 2-element case in push_swap.c:64-65, which simply swaps the top two elements.

​
Example: Two Sorted Numbers

./push_swap 3 5
Output
(no output - already sorted)

​
Sorting 3 Numbers

Three-number sorting uses the optimized sort_three() algorithm from push_swap.c:15-42.

​
Example: Reverse Order

./push_swap 3 2 1
Output
sa
rra
Explanation: This handles the case where val1 > val2 && val2 > val3 (line 24-28).
1

Initial State

Stack A: [3, 2, 1]
2

After sa

Stack A: [2, 3, 1]
3

After rra

Stack A: [1, 2, 3] ✓

​
Example: Maximum at Top

./push_swap 3 1 2
Output
ra
Explanation: When the largest value is at the top and needs to move to the bottom, a single rotation suffices (line 29-30).

​
Example: Two Swaps Needed

./push_swap 2 3 1
Output
sa
ra
Explanation: This handles val1 < val2 && val2 > val3 && val1 < val3 (line 35-39).

​
Sorting 5 Numbers

Five numbers trigger the sort_big_stacks() algorithm, which pushes elements to stack B, then sorts optimally.

​
Example: Random Order

./push_swap 5 3 1 4 2
Example Output
pb
pb
sa
pa
pa
ra
ra
The exact output depends on the implementation of sort_big_stacks(). The algorithm pushes elements to stack B, sorts stack A, then pushes back with optimal positioning.

​
Example: Nearly Sorted

./push_swap 1 2 3 5 4
Example Output
rra
sa
ra
ra
Nearly sorted inputs still require analysis to find the optimal solution.

​
Sorting 100 Numbers

For 100 random numbers, the algorithm must be efficient. The evaluation criteria typically requires:
  • Maximum ~700 operations for a “good” grade
  • Maximum ~900 operations for a “passing” grade

​
Example: Testing with Random Input

./push_swap $(seq 1 100 | shuf | tr '\n' ' ')
This generates 100 random numbers and pipes them to Push Swap.

​
Counting Operations

./push_swap $(seq 1 100 | shuf | tr '\n' ' ') | wc -l
Use wc -l to count the number of operations output.

​
Sorting 500 Numbers

The ultimate test of the algorithm’s efficiency:
  • Maximum ~5500 operations for a “good” grade
  • Maximum ~7000 operations for a “passing” grade

​
Example: Testing Performance

./push_swap $(seq 1 500 | shuf | tr '\n' ' ') | wc -l
For large inputs, the algorithm’s efficiency becomes critical. The Turk Algorithm (used in sort_big_stacks()) optimizes by:
  1. Calculating push costs for each node
  2. Identifying the cheapest move
  3. Positioning elements optimally before pushing

​
Understanding Good vs Bad Test Cases

​
Good Test Cases

Effective test cases reveal edge conditions: 
# All negative numbers
./push_swap -5 -2 -8 -1 -10

# Mix of positive and negative
./push_swap -3 0 3 -6 6

# Large value spread
./push_swap 2147483647 -2147483648 0

# Nearly sorted (worst case for some algorithms)
./push_swap 2 3 4 5 1

# Reverse sorted (common worst case)
./push_swap $(seq 100 -1 1)

​
Bad Test Cases

These don’t provide useful information: 
# Already sorted (trivial)
./push_swap 1 2 3 4 5

# Too small to test algorithm
./push_swap 1 2

# Single element (no sorting needed)
./push_swap 42

​
Benchmarking Your Implementation

Create a comprehensive test:
Test Script
#!/bin/bash

total=0
iterations=100

for i in $(seq 1 $iterations); do
    count=$(./push_swap $(seq 1 100 | shuf | tr '\n' ' ') | wc -l)
    total=$((total + count))
done

average=$((total / iterations))
echo "Average operations for 100 numbers: $average"
This script runs 100 tests and calculates the average operation count.

​
Visualization Tips

To better understand the algorithm:
  1. Use a checker program: Verify that your operations correctly sort the input
  2. Trace execution: Add debug output to see stack states
  3. Visualize operations: Create or use a visualizer to see rotations and pushes

​
Next Steps

Build docs developers (and LLMs) love

Get started for freeTalk to us