This is my push_swap project from the 42 cursus
The project involved the development of a data sorting algorithm using a stack and a limited set of instructions. The main objective was to sort the data with the minimum number of actions possible, which required extensive knowledge of various algorithms and optimization techniques. Through this project, I gained valuable experience in algorithm design and optimization, which helped to enhance my skills as a programmer.
- The game is composed of 2 stacks named A and B.
- To start with:
- A contains a random number of either positive or negative numbers without any duplicates.
- B is empty.
- The goal is to sort in ascending order numbers into stack A.
- To do this, you have the following operations.
sa- swap a: swap the first 2 elements at the top of stack a. (do nothing if there is only one or no elements).sb- swap b: swap the first 2 elements at the top of stack b. (do nothing if there is only one or no elements).ss- ss: swap a and swap b at the same time.pa- push a: take the first element at the top of b and put it at top of a. (do nothing if b is empty).pb- push b: take the first element at the top of a an dput it at top of b. (do nothing if a is empty).ra- rotate a: shift up all elements of stack a by 1. the first element becomes the last one.rb- rotate b: shift up all elements of stack b by 1. the first element becomes the last one.rr- rr: rotate a and rotate b at the same time.rra- reverse rotate a: shift down all elements of stack a by 1. the last element becomes the first one.rrb- reverse rotate b: shift down all elements of stack b by 1. the last element beoomes the first one.rrr- rrr: reverse rotate a and reverse rotate b at the same time.
Create two programs: checker and push_swap.
The checker program reads a random list of integers from the stdin, stores them, and checks to see
if they are sorted.
The push_swap program calculates the moves to sort the integers – pushing, popping, swapping and rotating
them between stack a and stack b – and displays those directions on the stdout.
You can pipe push_swap into checker, and checker will verify that push_swap's instructions were successful.
Both programs must mandatorily parse input for errors, including empty strings, no parameters, non-numeric parameters, duplicates, and invalid/non-existent instructions.
Push_Swap must conform to the 42 Norm.
Using normal libc functions is strictly forbidden. Students are however, allowed to use: write, read, malloc, free, exit.
It must not have any memory leaks. Errors must be handled carefully.
In no way can it quit in an unexpected manner (segmentation fault, bus error, double free, etc).
- In order to start sorting, my code pushes first two elements from top of the stack_a to the stack_b. By this way, we are creating one smallest number and one biggest number in stack_b. This is the prerequisites of my code. Because before pushing a number from stack_a to stack_b, one of the major thing the algorithm does is; comparing the number being pushed with the smallest number of stack_b and the biggest number of stack_b.
-
At this step, algorithm checks every number in stack_a. It searches the number which requires the minimum amount of operations in order to be placed at stack_b in correct spot.
-
After that, algorithm decides which number should be pushed, it calculates how many times it should rotate stack_a and how many times it should rotate the stack_b. Whicehever has the smallest number, algorithm rotates both of the stacks as the smallest number indicates. And it completes the rest of the rotates in the one single stack which ever stack required more rotate operation. You can watch how this step works in action here.
-
After this, algorithm pushed the number from the top of the stack_a to top of the stack_b. Every time this spot at stack_b is correct spot for the number thanks to the previous calculations.This pushing loop continues until only three elements are left in stack_a.
-
Algorithm quickly sorts the left three members in the stack_a.
- Every members in stack_b one by one are being pushed to the stack_a from top to the bottom. However, it checks everytime before the elements are being pushed. This continues until the stack_b is emptied.
- Finally, last time required amount of rotation is being applied in order to bring the smallest number on to the top of the stack_a.
