Welcome to Push_Swap, a modular and efficient sorting program designed to solve a fundamental algorithmic challenge: sorting integers using two stacks (a and b) with a limited set of operations. This project is part of the 42 Network curriculum and is designed to test your understanding of algorithms, data structures, and optimization.
- Introduction
- Project Structure
- Features
- Error Handling and Validation
- Bonus Functionality
- Installation
- Usage
- Makefile Specifics
- Acknowledgements
- Author
The Push_Swap project aims to implement efficient sorting algorithms with minimal operations. Using stacks (a and b), you must sort a list of integers by performing operations such as:
sa: Swap the first two elements of a stack.ra: Rotate a stack (top element moves to the bottom).pb: Push the top element from one stack to the other.
The bonus part introduces a checker program that validates the correctness of sorting operations.
.
├── include/ # Header files
│ ├── push_swap.h # Core declarations
│ ├── stack.h # Stack-specific structures and operations
├── src/ # Main source code
│ ├── core/ # Core logic for Push_Swap
│ ├── commands/ # Stack manipulation functions
│ ├── sorting/ # Sorting algorithms
│ ├── validation/ # Input parsing and validation
│ ├── utils/ # Utility functions
│ └── checker/ # Bonus checker implementation
├── libft/ # Custom library (libft) for common operations
├── tests/ # Test scripts and sample test cases
├── Makefile # Build automation
└── README.md # Project documentation- Clear separation of core logic, commands, sorting algorithms, validation, and utility functions.
- Reusable codebase for both mandatory and bonus parts.
- Supports both array-based and linked-list-based stacks for flexibility and performance.
- Small Inputs: Handles 3–5 numbers with hardcoded sorting.
- Large Inputs: Uses chunk-based or radix sorting to optimize moves.
The program ensures that inputs meet the following criteria:
- No duplicates.
- Valid integer representation (e.g.,
004is interpreted as4). - Handles invalid input such as
--or++.
- Frees all allocated memory, including stacks and auxiliary data structures, in case of errors.
- The bonus checker program reads operations from standard input and ensures:
- The stack is sorted.
- All operations are valid.
- Verifies the correctness of sorting operations.
- Reads operations like
sa,pb, etc., from standard input and applies them to the stacks.
- Uses
get_next_lineto handle multi-line input. - Outputs:
OKif the operations result in a sorted stack.KOif the stack is not sorted or operations are invalid.
- GCC: The GNU Compiler Collection.
- Make: Build automation tool.
- Clone the repository:
git clone https://github.com/kitearuba/push_swap.git
- Navigate to the project directory:
cd push_swap - Compile the project:
make
To sort a sequence of integers, run:
./push_swap <list_of_numbers>Example:
./push_swap 4 3 2 1Output:
pb
pb
ra
pa
paPipe the output of Push_Swap to the Checker:
./push_swap 4 3 2 1 | ./checker 4 3 2 1Expected Output:
- OK: Stack is sorted.
- KO: Stack is not sorted or invalid operations.
The Makefile:
- Avoids unnecessary relinking by checking timestamps of all dependencies.
- Rebuilds the project only when necessary, ensuring faster builds.
make: Builds the Push_Swap program and the Checker.make clean: Removes object files.make fclean: Removes object files and executables.make re: Rebuilds the entire project.
- 42 Network: For designing this challenging and rewarding project.
- Open-source contributors and the community for sharing insights and tips.
- chrrodri
GitHub Profile