42 Project Push Swap
The rules
- You have 2 stacks named a and b.
- At the beginning:
- The stack a contains a random amount of negative and/or positive numbers which cannot be duplicated.
- The stack b is empty.
- The goal is to sort in ascending order numbers into stack a. To do so you have the following operations at your disposal:
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 : sa and sb at the same time.
pa (push a): Take the first element at the top of b and put it at the top of a. Do nothing if b is empty.
pb (push b): Take the first element at the top of a and put it at the 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 : ra and rb 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 becomes the first one.
rrr : rra and rrb at the same time.
- I first joined all the contents inserted into one string separating by space.
- Then I chech if there is any invalid argument, which can be letter or anything outside number
- Then I check if there is duplicates and exit the program
- Then I create stack a based on the given numbers
- I partially used radix sorting technique. So I assign an index to each node in my stack. The index value is the position that the specfic node should be place if they were sorted. So, now I can totally forget about the real values and work only with the index number that I assigned.
THE SORTING ALGORITHM SORTING STARTS FROM HERE
- I check if the stack is already sorted. If so, simply exit else continue.
- check if the stack has two numbers. If so, do sa and exit.
- check if the stack has three numbers. If so, call the three numbers sorting function and do the sorting. else continue
- If stack_a has more than 3 elements then leave three items in stack_a and send everything to stack_b using mid_point algorithm. Once all the elements what are less than the first mid point are gone, we apply mid point algorith to the remaining onse. the mid point algorithm find mean(mid pt) of stack a and send all that are less than it to b if the top is not less than a, send it to back using ra.
- Once only three elements are left on stack a, we will sort them using the three number sorting function.
THE HIGHEST SORTING STARTS FROM HERE
while stack_b is not empty the following tasks will be repeated sequencailly
- find the current position of each element on stack a and stack b.
- Find total cost of putting the element to its position back in stack_a. which the cost of bringing the element to top of b and the cost of find the position of the element in a and changing its position to be at the top of stack_a.
- So, now we have the costs of all the elements in b. Now we select the element with the least cost.
- Finally we act the instructions of the element with list instructions