2.0 KiB
Pushswap
This is my implementation of the Pushswap project for the 42 school, using the radix sort algorithm.
Description
Pushswap is a sorting algorithm that sorts a list of integers using two stacks and a set of operations. The goal of the project is to implement the Pushswap algorithm in C and optimize the algorithm to sort the list using the minimum number of operations possible.
In this implementation, I used the radix sort algorithm, which sorts the list by comparing each digit of the integers in the list, from right to left. The algorithm sorts the integers by "bucketing" them based on their current digit value, and then repeating this process for each subsequent digit.
The project aims to develop students' problem-solving and algorithmic thinking skills, as well as their ability to optimize code for performance.
Usage
To use the program, first compile the push_swap executable by running make in the root directory of the project.
Then, run the program with a list of integers as arguments. For example: ./push_swap 4 67 -10 5.
The program will display a list of operations to sort the list, and the number of operations required.
Algorithm Overview
radix
The algorithm consists of the following steps:
- replace the value of the number by the index of the number
- put the number on the stack B if the n bit equal 0
- do the same for n + 1 while the stack was not sorted
Optimization
To optimize the algorithm, I used a combination of heuristics and algorithms, such as:
- Minimizing the number of operations by considering special cases, such as sorted or reverse-sorted lists
Through experimentation and testing, I was able to significantly reduce the number of operations required to sort the list.
Resources
- The project subject
- The C library documentation for the standard library functions used in the program
Authors
This project was created by Camille CHAUVET. If you have any questions or suggestions, feel free to contact me.