Push swap “ Easy Algorithm”

One or best push swap project algorithm in 42 / 1337 Coding school

In this blog, I will explain an algorithm That efficiently sorts the stack with fewer than 700 operations for 100 numbers and under 5500 for 500.

Before starting I want to share some of the good resources and things to know for the project.

• First, the project works with two stacks, so, of course, we need to understand what a stack is. Click here to understand.
• In this project, we also need to understand time complexity and how to calculate it. So, let me share some resources to help you learn about it: Big O notation, Time & space complexity.

Let’s explain some push swap rules, and know how we can move in and between the stacks:

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.

Both stacks are empty at the start. We first retrieve the arguments and parse them. After validating the input, we’re ready to begin.

First , we build our stacks A and B and fill A with the input we get.

To create our struct we need 2 variables content, index, and a pointer to point to the next node:

typedef struct stack

   int    content;
   int    index;
   struct stack *next;
} t_stack;

The first thing we need to do is index our node or numbers:

The index of each number is crucial in our algorithm. But how do we assign it efficiently?

It’s simple: find the smallest number in your list and assign it an index of 0, the second smallest gets 1, and so on.

Here’s an example to illustrate how this works::

Let’s start sorting part :

To achieve the best result, I break the sorting process into three parts: sorting for fewer than 5 elements, sorting for fewer than 100 elements, and sorting for more than 100 elements.

let’s start with three element sort:

We need to check only three things using the index:

If the index of the first element equals the maximum index, perform a RA: move the first element to the last position..

If the first element isn’t the largest, check if the second element is. Compare their index. if the second element has the maximum index, perform an RRA. This means the second element is the largest, so we move it to the last position and make the last element the first

After this step, we are sure the largest element is at the end. Now, we only need to check the first and second elements: if the first is larger than the second, perform a SA . otherwise, do nothing.

Let’s get some examples:

If the index of the first element is the maximum, perform a RA to move the first element to the last position.

The second condition doesn’t work because the index of the second element is not equal to the maximum index.

The final condition checks if the index of the first element is greater than that of the second. If so, perform a SA.

This is the same approach for all cases.

Now, let’s look at sorting four and five elements. I handle both cases using the same function. let me explain each step.

we have stack A with 5 numbers.

• The first step is to push the two smallest numbers from Stack A to Stack B.

At this point, in both cases (4 or 5 numbers), we have the two smallest numbers in Stack B. Now, we need to check the number of elements in Stack A:

• If Stack A has 3 elements, apply the sort-three algorithm to it.
• If Stack A has only 2 elements, check if the smaller one is on top:
• If it is, do nothing.
• Otherwise, perform SA.

In our case, we will sort Stack A using the three-number sorting algorithm.

Next, we check Stack B:

• If the larger number is on top, do nothing.
• Otherwise, perform SB to swap them.

This ensures that when we push elements back from Stack B to Stack A, the larger one is placed first, followed by the smaller one.

Now, we know how to correctly sort fewer than 6 numbers.

let’s tackle sorting for 100 or fewer numbers, and then for more than 100 numbers.

We will check what we need before starting:

Ofcaurse we need stacks A and B all the time.

And Range number i will explain what is it later.

Notice : The same function will sort both themes only the range will be different.

Sorting 100 or fewer numbers:

It will be separated into two steps.

Our function “Big_sort” handles the first step. Let me show you its prototype.

void big_sort(t_stack **stack_a, t_stack **stack_b, int range)
{
}

In our function, We will push all the elements from stack A to stack B but with a simple technique :

• We make stack A empty so the loop will stop when he is.
• Also, we need a variable “i” increment when we push an element start from 0.
• The range we can work with is 100 or less. Within this range, the values should be between 10 and 20, but I prefer using 15 or 18. (the range is just a number we depend on them to push the small and middle numbers first and the big of them next).

— Push process:

we push with two methods or two checking statements and we will take a lot of help from our index.

• 1- First, check if the element index is small or equal to ‘ i ’ if true push them to stack b directly and increment ‘ i ’. {do: pb}
• 2- second, check if the element is small or equal to ‘ i + Range ’, if yes push them to stack B and rotate stack B (make the first in the last). {do: pb rb}
• 3- If neither of our conditions apply, we simply rotate the stack. However, there are some special cases where we need to perform rrb. This happens when the stack is sorted from largest to smallest with a difference of 2, 3, or 4 between the numbers. In such cases, we need to check if more than half of the stack is sorted in this order. If so, perform rrb . otherwise, perform ra. My apologies, let’s leave this as the last thing to fix; for now, just do ra . {do : ra || rra}

Now we have all the numbers in stack B.

Let’s talk about how the numbers are sorted.

First, we push the smaller numbers to stack B. If we get a number smaller thanrange + i, we push it and place it at the end of the stack using pb rb. This almost makes smaller numbers come first and larger ones follow when i are small and makes sorting them easy.

But when i reaches a larger value, the first condition applies, and the larger numbers are pushed directly to the front of the stack. As a result, we end up with three parts: a section of large numbers at the front, followed by smaller numbers, and then another section for the remaining larger numbers. This doesn’t apply to all cases—when we have only 10 or 20 elements, there will only be two sections. Of course, the sections aren’t sorted, but this process makes it easier to push them back into stack A in sorted order.

• This will help you visualize the sections.

[embed]

• let’s take an example:

I don’t want to make this blog too long, so I’ve created a diagram of the process in draw.io. I’ll share the link to the diagram so you can view it.

“ Click on ‘Open with draw.io’ at the top to view the diagram ”

[embed]push_to_b.drawio.html Edit descriptiondrive.google.com

Now, we’re at the final step: we need to return all the elements, sorted, back to stack A.

• this process will be done by one function ‘final_sort’. its prototype will be

void final_sort(t_stack **stack_a, t_stack **stack_b)
{
}

It will be very simple we need to search for the big number in stack B, push it to stack A, and search again until stack B is empty.

The easiest method is to search for the large index and save it as variable ‘max’, and here also we have only three steps to do.

• 1- Check if the index of the first element is equal to ‘max’ if yes push them and dicrement ‘max’ {do: pa }
• 2- Check if the index of the second element equals max, if yes swap b (make the second one in the head) and push them. {do: sb pa}
• 3- If neither condition applies, we need to search for the element with the largest index and check if it’s in the first part of the stack. If it is, we use rb to move it with the smallest possible movement. If the element is in the second part of the stack, we use rrb to bring it to the front with minimal movement.

That’s all! I hope you find this helpful and benefit from it. If you have any questions or if something isn’t clear, feel free to leave your questions here. Also, here’s my GitHub , where you can find the code for this project.

[embed]Selboukaoui - Overview Dev . Selboukaoui has 10 repositories available. Follow their code on GitHub.github.com