This project is about sorting data. You have at your disposal a set of int values, 2 stacks and a set of instructions to manipulate both stacks. The final goal is to sort the data in ascending order with the lowest possible number of instructions.
The project is composed of two programs push_swap in Mandatory part and checker in Bonus part.
push_swapwhich we need to calculates and displays on the standard output the smallest list of instructions possible to sort the integer arguments received.checkerit's a program that takes integer arguments and reads instructions from the standard input. Once read, checker executes them and displays OK if integers are sorted. Otherwise, it will display KO or Error if the integers are not sorted or the instructions are not well formatted.
to start using the project, you need to clone the repository and run the following commands:
git clone https://github.com/whoismtrx/42_push_swap.git push_swap
cd push_swap
make
./push_swap 4 67 3 87 23
or
./push_swap "4 67 3 87 23"
or
arg="4 67 3 87 23" | ./push_swap $arg
./checker 4 67 3 87 23
pb
ra
pb
ra
sb
pa
pa
OK
- You should take arguments as a list of integers and nothing else.
- The program should not crash, even in case of error.
- You need to sort 3 numbers in less than 3 operations, 5 numbers in less than 12 operations and 100 numbers in less than 700 operations and 500 numbers in less than 5500 operations in case if you want to get 100/100.
- The project is composed of 2 stacks named
AandBand you can't use any other stack while sorting. - The sorting algorithm should be implemented with the instructions below:
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 think the first thing we need to care about is the data structure we gonna use. since stack doesn't implemented in the C standard library, we need to implement it by ourselves. we can use Arrays to implement it. we can also use Linked Lists but the best way to implement it specially for this project is to use Circular Doubly Linked Lists, because we can easily implement all operations with O(1) time complexity. The next thing we need to do, is to implement the instructions we gonna use to manipulate the stack. I'm not gonna dive deep into the implementation of the stack and the instructions because it's a basic thing and you can find a lot of resources on the internet to implement it so I'm considering that you already implemented it. After all, we can start to implement the sorting algorithm.
The first thing we need to do is to find the best algorithm to sort the stack with the lowest number of operations. let's check the size of the stack, if less or equal to 5, you can sort it with any basic algorithm you can think of. if more than 5, we can move to the next step.
To arrange the elements in the stack from smallest to largest, we need to assign each element a specific position. This process, known as indexing, helps us understand the order of the elements within the stack and the corresponding chunk they belong to. We can simplify the indexing step by incorporating it while adding elements to the stack.
Let's assume we start with a 0-based indexing system. When we push the first element onto the stack, we assign it an index of 0. As we proceed to push the second element, we compare its value with the first element. If the second element is smaller, we increase the index of the first element, while the second element retains an index of 0. On the other hand, if the second element is larger, we only increment its index, leaving the index of the first element unchanged. This process continues for all elements, ensuring that each one is assigned an index ranging from 0 to n-1. This indexed order helps maintain consistency and clarity within the stack.
if node->value > head->value
node->index++
else
head->index++
current = head->next
while current->next != head
if node->value > current->value
node->index++
else
current->index++
current = current->next
After we have all the elements indexed, we need to divide the stack into chunks. the best way to do this is to divide the stack into 3 chunks, and the first chunk it's the only one we gonna care about. So the first chunk will contain the first 1/3 of the elements, that means all the elements from 0 to (sizeof(stack A)/3)-1. and all those elements will be push to the secend stack B.
The elements with blue color it's our chunk.
As we seen in the previous step, we have a chunk of size sizeof(stack A)/3, we can notice that the size of stack A it's gonna change after we push the elements to the stack B, so we need to store this value in a variable let's call it Pivot_One, also because we need our algorithm to be more optimized, we need another variable we can name it Pivot_Two to store the half size of Pivot_One, so for know we have:
Pivot_One = sizeof(stack A)/3
Pivot_Two = Pivot_One/2
I know you are asking yourself why we need Pivot_Two? where going to figure it out in the next steps.
Now we decided the chunk we gonna care about, we have Pivot_one and Pivot_Two what's next? we need to set some conditions to know when we need to push an element to the stack B or rotate the stack A, we need another condition to know when we need to rotate the stack B after we push an element to it or not. Also because we have a Circular Doubly Linked List we need to have a condition to break the loop or we are going to have an infinite loop, we need a Counter to keep counting the number of elements we pushed to stack B to reinitialize the Pivot_One and Pivot_Two after we finish the first chunk. so let's set the conditions:
while sizeof(stack A) > 5
if top B index is <= Pivot_Two && sizeof(stack B) > 1
rotate the stack B
if top A index is <= Pivot_One
push the element to stack B
increment the Counter
else
rotate the stack A
if Counter >= Pivot_One
reinisialize the Pivot_One and Pivot_Two
reinisialize the Counter
After we push the chunk elements to the stack B.
keep in mind that we have a bunch of ways to implement those conditions, so you can implement them as you want. the most important thing is to know how to implement them on the right way to get the best results. after we finish this step, the counter will be equal to Pivot_One. so we know that we pushed all the elements from the first chunk to the stack B. to avoid the infinite loop, we need reinitialize the Pivot_One and Pivot_Two to get the next chunk. we can back to the Step 3 and repeat the process until we push all the elements to the stack B except the largest and the last 5 elements.
Stack A after we push the elements to the stack B.
Now we have all the elements pushed to the stack B exept the largest 5 elements, we can call the Basic algorithm to sort the stack A. After that, were going to the next step.
The Seventh step is the last one, we need to get back all the elements from the stack B to the stack A in the right order. we can do this by pushing the elements from the stack B to the stack A while we are checking the index of the elements, we gonna push the elements to the right position so basically the element with the top A index - 1 but if we keep looking for it in the stack with rotating, the number of operations will be so high, so to optimize this step we can push the elements to stack A even if not in the right position and we can keep them in the bottom of the stack A till we find the right position for them. also we need a variable to store the index of the element we keep in the bottom. so let's set the conditions:
while sizeof(stack B) > 0
lastIndex = 0
if bottom A index < top A index
lastIndex = bottom A index
if find(top A index - 1 in B) < sizeof(stack B) / 2
while top B index != top A index - 1
if top B index > lastIndex
lastIndex = top B index
push top B to A
rotate the stack A
else
rotate the stack B
push top B to A
else
while top B index != top A index - 1
reverse rotate the stack B
push top B to A
while lastIndex == top A index - 1
reverse rotate the stack A
this is how we get back the elements from the stack B to the stack A in the right position.
After we finish this step, we gonna have all the elements sorted in the stack A and we can print the instructions to the standard output.
-
firstly, don't look at my code as a solution, it's implemented 2 years ago and I'm sure it's not the best solution. I'm just trying to give you an idea about how you can implement the project in the right way.
-
secondly, in the previous steps, I try to write some pseudo code to help you understand the idea, there's a lot of ways to implement the conditions and the instructions, so you can implement them as you want.
-
thirdly, let's discuss the importance of the
Pivot_twoand the decision it makes aboutrotatingthe stack B. But why is this necessary? Let's consider what would happen if we didn't include it in our algorithm. If we implemented our algorithm without considering thePivot_twodecision, we would simply push all the elements from the first chunk onto stackBwithout performing anyrotations. However, when we eventually need to transfer these elements back from stackBto stackA, we would encounter a problem. Since we didn'trotatestackBduring the process, the elements would not be in the desired order. As a result, we would need to perform multiple rotations to rearrange the elements correctly. This is because some elements on stackBwould haveindexeslower than the ones we want to push onto stackA. Theseextra rotationswould significantlyincrease the number of operations required, making thealgorithm less efficient.this is how our algorithm gonna work without Pivot_Two.
So to avoid this issue, we introduce the
Pivot_twodecision to determine when and how to rotate stackB, ensuring that the elements are in the desired order before transferring them back to stackA. -
last but not least, i have a big thanks to my friend Nx21 for helping me to improve and optimize the algorithm. i wanna thank you for reading this article, I hope it helps you to understand the project and how you can implement it in the right way. if you have any question or you need help, feel free to ask me on my email
[email protected], and I will be happy to help you. also if you have any suggestion to improve the article or optimize the algorithm, please let me know.
