Push_swap is a sorting algorithm project that challenges the implementation of sorting a stack of integers using a limited set of operations. The goal is to sort the stack in ascending order with the minimum number of moves possible.
After compiling the project, run it with a list of integers:
./push_swap 3 2 1 5 4The program will output the sequence of operations needed to sort the stack:
pb
pb
sa
pa
paVerify the result using the provided checker:
./push_swap 3 2 1 5 4 | ./checker 3 2 1 5 4| Command | Description |
|---|---|
| sa | Swap the first two elements of stack A |
| sb | Swap the first two elements of stack B |
| ss | Perform sa and sb at the same time |
| pa | Push the first element of B to A |
| pb | Push the first element of A to B |
| ra | Rotate stack A (shift all elements up by 1) |
| rb | Rotate stack B (shift all elements up by 1) |
| rr | Perform ra and rb at the same time |
| rra | Reverse rotate stack A (shift all elements down by 1) |
| rrb | Reverse rotate stack B (shift all elements down by 1) |
| rrr | Perform rra and rrb at the same time |
This project was implemented using radix sort adapted for stack operations. The decision to use radix sort was based on several factors:
- Predictable performance: Radix sort guarantees O(n × k) complexity, where k is the number of bits, ensuring consistent behavior across different input sizes.
- Stable operation count: Unlike comparison-based algorithms, radix sort produces a reliable number of moves regardless of the initial stack order.
- Natural fit for stacks: Bit-by-bit sorting naturally translates to push/pop operations between two stacks.
- Scalability: The algorithm handles large datasets (500+ elements) efficiently without performance degradation.
- Simplicity: The logic is straightforward to implement and debug compared to more complex sorting strategies.
The radix sort implementation follows these steps:
- Parsing and validation – Input integers are checked for errors and duplicates.
- Index mapping – Numbers are converted to normalized indices (0 to n-1).
- Bit-by-bit sorting – The algorithm examines each bit position from LSB to MSB.
- Stack distribution – Elements are pushed to stack B or kept in stack A based on the current bit value.
- Reconstruction – After processing each bit, elements are pushed back to stack A in sorted order.
- Implementing sorting algorithm with stack operations
- Working with stack data structures
- Algorithm optimization and complexity analysis
- Bit manipulation techniques in C
- Parsing and validating input data
- Adapting non-comparison sorting to constrained environments
- Strengthening algorithmic thinking in C