algorithmsortingstacklanguage-agnosticpush-swap# Push_swap: what is the most efficient way to sort given values using a limited set of instructions on two rotatable stacks?

## Algorithm

I have an inferior solution for the push_swap project for school 42:

You have at your disposal a set of int values, 2 stacks and a set of instructions to manipulate both stacks.

Write [a program] in C:

[...] called

`push_swap`

which calculates and displays on the standard output the smallest program using`Push_swap`

instruction language that sorts integer arguments received: [...]

`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 know an almost identical question as already been asked here, but I do not find the provided answers to be very helpful since the goal of the exercise was not clearly stated in the question (in its original version).

I have designed a simple algorithm to solve the exercise described above, but it is too slow. How can I improve it or design a more efficient algorithm?

The goal of the exercise is to find the shortest list of stack instructions such that when followed, stack A is sorted. **What matters most is the size of the list, not the complexity of the algorithm we use to find such a list.**

For now I have implemented this very simple algorithm :

- Gather all the numbers in the array and sort it such that the smallest number is at index 0.
- Take the first number in the sorted array, we'll call it x. We need to move x to the top of the stack then push it to B so :
- If x is in second position, swap.
- If x is closer to the top of the stack, rotate until x is on top.
- If x is closer to the bottom of the stack, reverse until x is on top.

- After each operation check if the stack is sorted.
- If it is not, push the first element of the stack onto B, take the next element in the array and repeat.

- When only two elements are left in A, check if they are ordered, if not swap them.
- Push all the elements from B back onto A.

This algorithm works pretty well when n is small but takes way too long when n gets large. On average I get :

- 30 instructions for n = 10.
- 2500 instructions for n = 100.
- 60000 instructions for n = 500.
- 250000 instructions for n = 10000.

I would like to go below 5000 steps for n = 500 and below 500 steps for n = 100.

Solution

The question needs to be edited. The exercise is called "push swap", a project for students at school 42 (non-accredited school). A second part of the project is called "checker" which verifies the results of "push swap".

Here is a link that describes the push swap challenge | project. Spoiler alert: it also includes the authors approach for 100 and 500 numbers, so you may want to stop reading after the 3 and 5 number examples.

The term stack is incorrectly used to describe the containers *a* and *b* (possibly a French to English translation issue), as swap and rotate are not native stack operations. A common implementation uses a circular doubly-linked list.

push swap: input a set of integers to be placed in *a*, and generate a list of the 11 operations that results in *a* being sorted. Other variables and arrays can be used to generate the list of operations. Some sites mention no duplicates in the set of integers. If there are duplicates, I would assume a stable sort, where duplicates are to be kept in their original order. Otherwise, if going for an optimal solution, all permutations of duplicates would need to be tested.

checker: verify the results of push swap.

Both programs need to validate input as well as produce results.

One web site lists how push swap is scored.

```
required: sort 3 numbers with <= 3 operations
required: sort 5 numbers with <= 12 operations
scored: sort 100 numbers with <= 700 operations max score
900 operations
1100 operations
1300 operations
1500 operations min score
scored: sort 500 numbers with <= 5500 operations max score
7000 operations
8500 operations
10000 operations
11500 operations min score
```

The following gives an idea of what is allowed in an algorithm to generate a list of operations. The first step is to convert the values in *a* into ranks (the values are never used again). In the case of duplicates, use the order of the duplicates when converting to ranks (stable sort), so there are no duplicate ranks. The values of the ranks are where the ranks belong in a sorted array:

```
for(i = 0; i < n; i++)
sorted[rank[i]] = rank[i].
```

For example, the values {-2 3 11 9 -5} would be converted to {1 2 4 3 0}: -2 belongs at sorted[1], 3 at sorted[2], ..., -5 at sorted[0]. For a stable sort where duplicates are allowed, the values {7 5 5 1 5} would be converted to {4 1 2 0 3}.

If *a* has 3 ranks, then there are 6 permutations of the ranks, and a maximum of 2 operations are needed to sort *a*:

```
{0 1 2} : already sorted
{0 2 1} : sa ra
{1 0 2} : sa
{1 2 0} : rra
{2 0 1} : ra
{2 1 0} : sa rra
```

For 5 ranks, 2 can be moved to *b* using 2 operations, the 3 left in *a* sorted with a max of 2 operations, leaving at least 8 operations to insert the 2 ranks from *b* to into *a*, to end up with a sorted *a*. There only 20 possible ways to move 2 ranks from *b* into *a*, small enough to create a table of 20 optimized sets of operations.

For 100 and 500 numbers, there are various strategies.

Spoiler:

Youtube video that shows 510 operations for n=100 and 3750 operations for n=500.

https://www.youtube.com/watch?v=2aMrmWOgLvU

Description converted to English:

`Initial stage : - parse parameters - Creation of a stack A which is a circular doubly linked list (last.next = first; first.prec = last - Addition in the struct of a rank component, integer from 1 to n. This will be much more practical later. Phase 1 : - Split the list into 3 (modifiable parameter in the .h). - Push the 2 smallest thirds into stack B and do a pre-sort. do ra with others - Repeat the operation until there are only 3 numbers left in stack A. - Sort these 3 numbers with a specific algo (2 operations maximum) Phase2: (Only the ra/rra/rb/rrb commands are used. sa and sb are not used in this phase) - Swipe B and look for the number that will take the fewest moves to be pushed into A. There are each time 4 ways to bring a number from B to A: ra+rb, ra+rrb, rra+rb, rra+rrb. We are looking for the mini between these 4 ways. - Then perform the operation. - Repeat the operation until empty B. Phase 3: If necessary rot stack A to finalize the correct order. The shorter between ra or rra. The optimization comes from the fact of the maximum use of the double rotations rr and rrr`

Explanation:

`Replace all values in`

aby rank. For n = 100, a 3 way split is done: ranks 0 to 32 are moved to the bottom ofb, ranks 33 to 65 are moved to the top ofb, leaving ranks 66 to 99 ina. I'm not sure what is meant by "pre-sort" (top | bottom split inb?). Ranks 66 to 99 inaare sorted, usingbas needed. Ranks frombare then inserted intoausing fewest rotates. For n = 500, a 7 way split is done: Ranks 0 to 71 moved to bottom ofb, 72 to 142 to top ofb, which will end up in the middle ofbafter other ranks moved tob. Ranks 143 to 214 to bottom ofb, 215 to 285 to top ofb. Ranks 286 to 357 to bottom of`b`

, 358 to 428 to top of`b`

. Leaving ranks 429 to 499 ina. The largest ranks inbare at the outer edges, smallest in the middle, since the larger ranks are moved into sortedabefore smaller ranks. Ranks inaare sorted, then ranks frombmoved intoausing fewest rotates.

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array