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 OP.
I have designed a simple algorithm to solve the exercise described below, but I would like help in order to improve it or design a more efficient one.
Exercise
Given a stack A filled with n random integers (positive and/or negative) with no duplicates, an empty stack B and the eleven instructions listed below, print to the screen the shortest list made out of those instructions only such that when all the instructions are followed in order, A is sorted (the smallest number must be on top of the stack).
- sa : swap a - swap the first 2 elements at the top of stack a
- sb : swap b - swap the first 2 elements at the top of stack b.
- 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.
- pb : push b - take the first element at the top of a and put it at the top of b.
- 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.
The goal of the exercise if to find the shortest list of stack instructions such that when followed 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.
CodePudding user response：
This is a variation on https://stackoverflow.com/a/38165541/585411 which you already rejected. But hopefully you'll understand my explanation of how to do a bottom up mergesort better.
A run is a group of numbers in sorted order. At first you have many runs, presumably most are of small length. You're done when you have one run, in stack A.
To start, keep rotating A backwards while the bottom element is <= the top. This will position the the start of a run at the top of A.
Next, we need to split the runs evenly between A and B. The way we do it is go through A once, looking for runs. The first run goes at the bottom of A, the second run goes at the bottom of B, and so on. (Placing at the bottom of A just needs ra until the run is done. Placing at the bottom of B means pb then rb.)
Once we've split the runs, we either just placed a run at the bottom of A and A has one more run than B, or we just placed a run at the bottom of B and they have the same number of runs.
Now start merging runs, while you continue switching between A and B. Every time you merge, if you merged to A then A wound up with one more run. If you merged to B you have the same number of runs.
Merging a run to B looks like:
if top of A < top of B:
pb
rb
while bottom of B <= top of B:
if top of A < top of B:
pb
rb
while bottom of B <= top of A:
pb
rb
Merging a run to A is similar, just reversing the roles of the stacks.
Continue until B is empty. At that point B has 0 runs, while A has one. Which means that A is sorted.
This algorithm will take O(n log(n)) comparisons.
The problem has changed a lot since I first answered, so here are ideas for optimizations.
First, when splitting, we can do better than just dealing runs to A and B. Specifically we can put rising runs at the bottom of A, and push falling runs onto B (which leaves them rising). With an occasional sa to make the runs longer. These operations can be interleaved, so, for instance, we can deal out 5 2 3 1 4 with pb ra ra pb ra and then merge them with pa ra ra ra pa ra thereby sorting it with 11 operations. (This is probably not optimal, but it gives you the idea.) If you're clever about this you can probably start with an average run length in both piles of around 4 (and maybe much better). And during the splitting process you can do a lookahead of several instructions to figure out how to efficiently wind up with longer runs. (If you have 500 elements in runs of 4 that's 125 runs. The merge sort pass now should be able to finish in 7 passes.)
Are we done finding potential optimizations? Of course not.
When we start the merge passes, we now have uneven numbers of runs, and uneven numbers of elements. We are going to merge pairs of runs, place them somewhere, merge pairs again, place them somewhere, etc. After the pass is done, we'd like two things to be true:
- The average length of run in both stacks should be about the same (merging runs of similar lengths is more efficient).
- We want to have used as few operations as possible. Since merging
nintomtakes2n moperations, it matters where we put the merge.
We can solve for both constraints by using dynamic programming. We do that by constructing a data structure with the following information:
by the number of merged runs created:
by the number of runs put in `A`
by the number of elements put in `A`
minimal number of required steps
last stack merged into
We can then look through the part with the largest number of runs created, and figure out what makes the average run size as close as possible. And then walk back to figure out which sequence of merges got there in the minimum number of steps. And then we can work out what sequence of steps we took, and where we wound up.
When you put all of this together, I'm dubious that you'll be able to sort 500 elements in only 5000 steps. But I'd be surprised if you can't get it below 6000 on average.
And once you have all that, you can start to look for better optimizations still. ("We don't care how much analysis is required to produce the moves" is an invitation to spend unlimited energy optimizing.)
CodePudding user response：
Example C test program. SQ is a stack|queue class. It uses a circular array with a size of power of 2, using a bit mask to cause the indexes to wrap around. Indexes are pre-decremented or post-incremented.
There are defines for the operations. For example, PARA is a combined PA RA. All of the operations are implemented as pop_front, push_back.
The sort() function is a bottom up merge sort for queues.
For 500 elements, total number of operations is 7470 non-stable or 7518 stable. There is a define for stable option.
#include <iostream>
#define MAXSIZ (64*1024ull) // max stack size
#define IDXMSK (MAXSIZ-1) // index mask
class SQ{ // stack | queue
int *sq; // ptr to array
size_t head;
size_t tail;
size_t cnt;
public:
SQ(){ // constructor
sq = new int[MAXSIZ];
head = tail = cnt = 0;
}
~SQ(){ // destructor
if(sq != NULL)
delete[] sq;
}
void swap(SQ &other) {
std::swap(this->sq, other.sq);
std::swap(this->head, other.head);
std::swap(this->tail, other.tail);
std::swap(this->cnt, other.cnt);
}
size_t size(){
return cnt;
}
int front(){
return sq[head];
}
int back(){
return sq[(tail - 1)&IDXMSK];
}
void push_front(int i){
cnt ;
head = (head - 1)&IDXMSK;
sq[head] = i;
}
void push_back(int i){
cnt ;
sq[tail] = i;
tail = (tail 1)&IDXMSK;
}
int pop_front(){
cnt--;
int i = sq[head];
head = (head 1)&IDXMSK;
return i;
}
int pop_back(){
cnt--;
tail = (tail - 1)&IDXMSK;
return sq[tail];
}
};
int rnd32()
{
static unsigned int r = 0;
r = r*1664525 1013904223;
return (int)r;
}
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
static size_t paracnt;
static size_t pbrbcnt;
static size_t racnt;
static size_t rbcnt;
#define PARA {a.push_back(b.pop_front()); paracnt ;}
#define PBRB {b.push_back(a.pop_front()); pbrbcnt ;}
#define RA {a.push_back(a.pop_front()); racnt ;}
#define RB {b.push_back(b.pop_front()); rbcnt ;}
#define STABLE 0 // 0|1 = not stable | stable
void sort(SQ &a, SQ &b)
{
size_t i;
size_t r = 1; // run size
size_t as, bs, sz; // stack sizes
size_t ar, br; // run sizes
bool d; // destination T|F = a|b
sz = a.size(); // split up data
if(sz < 2)
return;
for(i = 1; i < sz; i = 2){
RA
PBRB
}
if(sz&1)
RA
while(1){
#if STABLE
d = true;
#else
d = (a.size() <= b.size()); // set initial destination
if((r r) >= sz) // if last pass merge to a
d = true;
#endif
as = a.size();
bs = b.size();
while(1){ // merge a pair of runs
ar = MIN(r, as);
br = MIN(r, bs);
while(1){
if(ar == 0){
while(br){
if(d) PARA else RB
br--;
bs--;
}
break;
}
if(br == 0){
while(ar){
if(d) RA else PBRB
ar--;
as--;
}
break;
}
if(a.front() <= b.front()){
if(d) RA else PBRB
ar--;
as--;
} else {
if(d) PARA else RB
br--;
bs--;
}
}
d ^= 1; // toggle destination
if(as == 0 && bs == 0)
break;
}
r = r r;
if(a.size() == 0 || b.size() == 0)
return;
}
}
#define COUNT 500
//----------------------------------------------------------------------//
// main //
//----------------------------------------------------------------------//
int main()
{
SQ a;
SQ b;
int i;
int x;
for(i = 0; i < COUNT; i )
a.push_front(rnd32());
sort(a, b);
if(a.size() != COUNT){
std::cout << "a.size() != COUNT" << std::endl;
return 0;
}
x = a.pop_front();
for(i = 1; i < COUNT; i ){
if(x > a.front())
break;
x = a.pop_front();
}
if(i == COUNT)
std::cout << "passed" << std::endl;
else
std::cout << "failed" << std::endl;
std::cout << "count: " << (paracnt*2) (pbrbcnt*2) racnt rbcnt << std::endl;
return 0;
}