Sorting with stacks

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Ed boy
Posts: 12
Joined: Wed Mar 23, 2011 6:28 pm UTC

Sorting with stacks

Postby Ed boy » Wed Oct 29, 2014 11:10 pm UTC

This might be the wrong place to post this, and I apologize if that's the case.

This is also a problem that I would have expected to already have some research done on it, but any attempts at researching sorting problems gives me research into problems where computing operations is what we wish to minimize, but that is not the case here.

Suppose we have a set of N stacks that we can use. We also have x different cards, each with a number written on them (there may be multiples). The cards start out in stack 1, in a known order. Our desired end state is to have all the cards in stack N in a sorted order. In order to do this, we have a robot that can move the top card of any stack onto the top of any other stack.

We wish to find a series of instructions to give to the robot such that the number of total card movements that the robot performs is minimized. The amount of time that it takes to compute what the optimal series of instructions is is pretty irrelevant - compared to the time required to physically move the cards, the computation time will be negligible.

One can construct upper and lower bounds for how many movements will be required. obviously, each card will need to be moved at least once, so there will be at least x movements required. Similarly, there exists an algorithm for the N=3 case (and therefore for every other case with N>2) that requires at most x(x+1)/2 card movements. Similarly, we can show that the problem is unsolvable for N<3.

One can also consider the problem where the cards and unknown and can only become known by picking them up with the robot. This is also of interest, but we can turn it into the first one with only x movements, so finding a good algorithm for the first problem gives us a good algorithm for this one.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Sorting with stacks

Postby jaap » Thu Oct 30, 2014 3:27 am UTC

Let's get the obvious algorithm out of the way:
1) split the x cards into N-2 approximately equal stacks, each with about x/(N-2) cards. The two empty stacks are the goal stack (where the sorted cards will be placed) and a spare stack.
2) Use the 3-stack algorithm you mention on the N-2 smaller stacks. I.e. repeatedly extract the next card you need from whatever stack it is in by transferring that stack to the spare stack, except for that one card that you put on the goal stack.

For simplicity, let y be equal to ceil(x/(N-2)), which is the number of cards in the largest stacks after step 1. This step takes x-y moves, or x moves if you need to find out the card order too.
In step 2, each stack will be involved in at most y*(y+1)/2 moves.
This gives a total of at most x-y+(N-2)*y*(y+1)/2 moves.

For large x, this algorithm is about 1/(N-2) times the length of the 3-stack algorithm.


I expect there are much more efficient algorithms. For example something reminiscent of merge sort seems likely, where you first somehow construct up to N-1 stacks of cards, each sorted in reverse order, which you can then merge onto the goal stack in sorted order in x moves. Unfortunately I don't know of any published research for this specific problem.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests