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_swapwhich calculates and displays on the standard output the smallest program usingPush_swapinstruction language that sorts integer arguments received: [...]
sa: swapa- swap the first 2 elements at the top of stacka. Do nothing if there is only one or no elements).sb: swapb- swap the first 2 elements at the top of stackb. Do nothing if there is only one or no elements).ss:saandsbat the same time.pa: pusha- take the first element at the top ofband put it at the top ofa. Do nothing ifbis empty.pb: pushb- take the first element at the top ofaand put it at the top ofb. Do nothing ifais empty.ra: rotatea- shift up all elements of stackaby 1. The first element becomes the last one.rb: rotateb- shift up all elements of stackbby 1. The first element becomes the last one.rr:raandrbat the same time.rra: reverse rotatea- shift down all elements of stackaby 1. The last element becomes the first one.rrb: reverse rotateb- shift down all elements of stackbby 1. The last element becomes the first one.rrr:rraandrrbat 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 :
This algorithm works pretty well when n is small but takes way too long when n gets large. On average I get :
I would like to go below 5000 steps for n = 500 and below 500 steps for n = 100.
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 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 ofb, 358 to 428 to top ofb. 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.