Create a program such that, with a given a set of instructions, sorts n numbers into a stack in ascending order as efficiently as possible. The program must display the set of instructions used to sort the given numbers and the input is validated with the program 'checker_linux'. For more information about sorting instructions and rules refer to "subject.pdf".
./push_swap <set_of_numbers> or ./push_swap n1, n2, n3..., n
- Learn about Big O notation.
- How to optimize a sorting algorithm.
- Adapt existing algorithms (Quicksort, Insertion Sort, Merge Sort...) to the current enviroment.
- Use the main ideas of other algorithms to create a new algorithm that suits the needs of the required task.
Although the idea about this project is to learn about algorithmic complexity, the actual "efficiency" of the algorithm is not measaured by the time it takes to sort the numbers, but by the number of instructions. Regardless of this measure, execution time is also taken into account so that the program has a balanced time/output ratio.
I've included a bash script (linux) that simply tries with n random numbers and loops m number of times. At the end of the script, it will display the stats of all the tests (max/min number of instructions and average number of instructions).
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). The MIT Press.
Ogun, A. Y. (2023, September 8). Push swap - A journey to find most efficient sorting algorithm. Medium. https://medium.com/@ayogun/push-swap-c1f5d2d41e97
https://automatic-saltopus-34b.notion.site/push_swap-c15e62229b9541d78fadec4d6aae8b50
125/125