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?


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.

Algorithm

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.

    https://medium.com/@jamierobertdawson/push-swap-the-least-amount-of-moves-with-two-stacks-d1e76a71789a

    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 a by rank.
    For n = 100, a 3 way split is done:
    ranks 0 to 32 are moved to the bottom of b,
    ranks 33 to 65 are moved to the top of b,
    leaving ranks 66 to 99 in a.
    I'm not sure what is meant by "pre-sort" (top | bottom split in b?).
    Ranks 66 to 99 in a are sorted, using b as needed.
    Ranks from b are then inserted into a using fewest rotates.
    For n = 500, a 7 way split is done:
    Ranks 0 to 71 moved to bottom of b, 72 to 142 to top of b, which
    will end up in the middle of b after other ranks moved to b.
    Ranks 143 to 214 to bottom of b, 215 to 285 to top of b.
    Ranks 286 to 357 to bottom of b, 358 to 428 to top of b.
    Leaving ranks 429 to 499 in a.
    The largest ranks in b are at the outer edges, smallest in the middle,
    since the larger ranks are moved into sorted a before smaller ranks.
    Ranks in a are sorted, then ranks from b moved into a using fewest rotates.