A sorting puzzle for geeky types

Miscellaneous and Personal Stuff I Must Share
1

I was inspired to post this by a question about sorting algorithms over in GQ, but since this isn’t so serious I’m posting over here in MP to start.

This is a question I first thought about in university, playing around with a deck of cards and thinking about the sorting stuff I was learning in my programming classes. Basically, it’s attempting to sort in a very minimalist environment.

The three-stack sorting puzzle

You start with a huge number of elements on one stack, in an unspecified order. You may do any of the following things:

  • Move elements from one stack to another, out of three available: A, B, and C. (As a convention, elements start on stack A)
  • Test to see if a stack is empty
  • If two stacks are both non-empty, then test to see if one is less than or greater than the other.
  • Set or unset a single memory flag
  • Test the status of the flag.

And of course, you can use control structures, loops and case statements, as you please. (Even subroutines or functions, except you can’t use them to create any other data space than the three stacks and the flag.)

The objective: to design an efficient algorithm under these conditions to sort the elements in ascending order on a single stack. (If elements are equal, then their order is unimportant.) You can sort to any stack you please.

I’ll provide the code for a bubble sort as an example. Selection sort and insertion sort are also fairly easy to implement in three-stack, (at least I found it so,) but the traditional recursive algorithms for mergesort or quicksort are completely infeasible. I’ve found one solution for O(n log n) time - maybe dopers can work out another!

Three-stack bubble sort

(Unsorted elements start on stack A)

DO
unset flag
DO
moveFrom A to B

	If isEmpty(A) then EXIT DO
	
	If top(A) < top(B) then
		moveFrom B to C
		moveFrom A to B
		moveFrom C to A
		
		set flag
	end-if
	
LOOP

DO while not isEmpty(B)
	moveFrom B to A
LOOP

if flag is unset then EXIT DO

LOOP

return A
If you have questions, please ask away.

2

That’s the Towers of Hanoi problem, and it’s an elementary exercise for people taking Data Structures.

:yawns:

3

Hmm… there are similarities to the towers of hanoi, as I understand it, but it’s not identical to any ‘elementary problem’ involving them that I remember. For instance, the restriction in towers that you can’t put an element of higher value temporarily on top of that of a lower value is eliminated here - in fact, at the beginning it’s almost guaranteed that some elements will be ‘upside down’ on the initial stack

Also, with ToH you can see the full contents of all three towers and calculate your sequence of moves accordingly, IIRC. Here, you can only look at the top element of each of the three ‘towers’ at any one moment.

But if I’m wrong and the solution is so ‘elementary’ in spite of these differences, them please enlighten me, oh master of data structures.

:wink:

4

No it isn’t. The Towers of Hanoi problem has the additional constraint that a larger element can’t be placed on top of a smaller element.

5

I have a C++ ToH program I wrote sitting on my PC at home. Since I’m at work now, you’re screwed for a while. :stuck_out_tongue:

6

I wait with eager anticipation. :slight_smile:

7

In the meantime, linky to a classic implementation. Mine has more code than this but is similar overall, written thusly so I could see the block movements in enough detail to satisfy my curiosity.

8

To help clarify the nature of the problem, I’m posting a sample run-through of the bubble sorting algorithm with a very small amount of data, and a few comments. Maybe this will dispel the notion that it’s just tower of hanoi in another guise. :smiley:



START:
A:  B:  C:  flag-off
 4
 8
 5
 6

Move the first item from A to B
A:  B:  C:  flag-off
 8   4
 5
 6

Since top of B is less than top of A, move another over.
A:  B:  C:  flag-off
 5   8
 6   4
 
Now we need to do our first bubble-swap, using C as a temporary space.
A:  B:  C:  flag-off
 5   4   8
 6

A:  B:  C:  flag-off
 6   5   8
     4

A:  B:  C:  flag-on
 8   5
 6   4

Because we've done a swap, the flag is now on, indicating that the list wasn't already sorted.
Move the 8 over again, triggering another bubble swap
A:  B:  C:  flag-on
 6   8
     5
     4

A:  B:  C:  flag-on
 6   5   8
     4

A:  B:  C:  flag-on
     6   8
     5
     4

A:  B:  C:  flag-on
 8   6
     5
     4

Now we move 8 over, and that's the last of A, so we move everything back
A:  B:  C:  flag-on
     8
     6
     5
     4
     
A:  B:  C:  flag-on
 8   6
     5
     4

A:  B:  C:  flag-on
 6   5
 8   4
 
A:  B:  C:  flag-on
 5   4
 6
 8

Now we turn the flag off and start over again.
A:  B:  C:  flag-off
 4
 5
 6
 8

A:  B:  C:  flag-off
 5   4
 6
 8

A:  B:  C:  flag-off
 6   5
 8   4

A:  B:  C:  flag-off
 8   6
     5
     4

A:  B:  C:  flag-off
     8
     6
     5
     4

Everything was moved over without having to turn the flag on, so we can move everything back to A and be done.
A:  B:  C:  flag-off
 8   6
     5
     4

A:  B:  C:  flag-off
 6   5
 8   4

A:  B:  C:  flag-off
 5   4
 6
 8

A:  B:  C:  flag-off
 4
 5
 6
 8

DONE.

Rysto, any interest in trying your hand at a selection sort? :slight_smile:

9

The Tower of Hanoi algorithm won’t work unless stack A is already sorted. Say that you have a four-element stack of [2, 3, 4, 1] and you’re trying to move it to stack C. You put the 2 on stack B, the 3 on stack C, the 2 on stack C, the 4 on stack B, and then you have no more legal moves.

If you modify it so that it’s allowed to ignore comparisons when moving an element to stack A, it should be OK. But it’s still nowhere near as efficient as the bubblesort that the OP presented.

ETA: It might be interesting to try to modify the OP’s algorithm so that the sorted list ends up on stack C. I’ll take a look at it.

10

Interestingly, it’s easy enough to do the first pass of a quicksort… take the top element of A and put it in B. Then for each element in A, if it’s greater than B, put it in C. If it’s less than B, do B->C, A->B, C->B. You end up with a stack on B all of which is less than everything in the stack on C. At that point, if you could either (a) have a local variable to store a single int, or (b) have the ability to “mark” and “unmark” any element (ie, put a post-it on a tile, and then check for it); you can recurse and finish the quicksorting. Without that, though, I think you might be stuck.

11

Hmm… you also have to ‘remember’ the value of A and hold it for comparisons in order to do the partition in the first place.

I’m intrigued by your ideas though… if you had an int variable, what would you be doing with it? I can see using two, first incrementing one, then incrementing another and comparing to it.

How about, instead of post-its, the ability to push and pop ‘blank’ stack elements as markers? You can test to see if the top of a stack is blank like you test for emptiness, and have to remove all of your blanks before completing the sort.

I’m afraid I can only offer a constant number of blank stack elements though, say 3. Is that going to be a problem? :smiley:

And, would anybody like to see some more of the algorithms I’ve worked out? :slight_smile:

12

No. You push it onto B, and then always leave it on top of B. When you need to put something into B, you do B->C, A->B, C->B so that the “divider” still ends up on top.

I don’t think 3 is adequate to do a quicksort. I think I need an arbitrary number, to partition my “temporary” use of one of the piles from the remainder of the pile beneath. A 4th pile would be adequate also.

13

Given a single int, I’m pretty sure that you can do mergesort. You can definitely do it with 2 ints.

14

Okay, yeah, that ‘swapunder’ technique to leave your pivot on top of B will work. I didn’t think of that one.

A fourth stack would be interesting I admit - how would you go about quicksorting with that??

15

Mergesort would be extremely easy to implement, though it wouldn’t end up being recursive.[list=#][li]Stack A has all cards, stacks B and C are empty.[/li][li]Put cards from A onto B while they are in order.[/li][li]Put cards from A onto C while they are in order.[/li][li]Merge stacks B & C onto A.[/li]Repeat from step one until fully sorted.[/list]

16

That’s not mergesort; it has a worst case time of O(n^2).

17

Oh please. It’s as mergesorty as you’re gonna get with an artifical three stack limitation.

It’s not like the quicksort described in post 10 is an actual quicksort, or the bubblesort proposed by the OP is an actual bubblesort. Why single out my method for criticism?

18

Okay, trying again. (I had a lot of another post worked out and then decided to start over.) Ellis Dee, I think that you are trying to describe a very good algorithm for this problem that I believe works in O(n lgn) time, though it isn’t the traditional recursive mergesort most often described in textbooks. However, you didn’t really describe it well enough to be clear, so I’ll take a try.

Starting from A, you deal out to B and C trying to form the longest descending sequences on those stacks (from the top down) as possible - at first this will require a lot of decision making, but once you’ve already done this a few times and got some good sequences on A all this will amount to is alternating the existing sequences back and forth from one stack to the other.

Then, you deal from B and C back to A, merging two sequences in order (in reverse order now that you’re going through the stacks the other way, but this doesn’t really matter.) Once one stack is empty, you simply move everything from the other back to A.

Repeat this until everything gets dealt out only to stack B from A (and is therefore in a single sorted sequence.) You can return from B or A as you wish.

The reason that it’s O(n lgn) is that the length of the sorted sequences, which start as small constants (1-3 cards,) will tend to double every time you deal back and forth. One deal out and back should take O(n) time, and you will need about log(2)n repetitions for the sequences to keep doubling until they are of length n - and therefore the entire stack is sorted.

Does that sound reasonable?

19

I am ignorant of math beyond the remedial highschool level, so some of your analysis is over my head. Broad strokes, though, yeah, that’s about it. To use your initial shuffle as an example: (Horizontally instead of vertically.)

While A != Null And (B = Null Or A > B), move from A to B
A: 4, 8, 5, 6 (B = Null, so move from A to B)
B: Null
C: Null

A: 8, 5, 6 (8 > 4, so move from A to B)
B: 4
C: Null

A: 5, 6 (5 !> 8, so move on to next step)
B: 8, 4
C: Null

While A != Null And (C = Null Or A > C), move from A to C
A: 5, 6 (C = Null, so move from A to C)
B: 8, 4
C: Null

A: 6 (6 > 5, so move from A to C)
B: 8, 4
C: 5

A: Null (A = Null, so move on to next step)
B: 8, 4
C: 6, 5

Merge back to A (If B > C Move B to A, Else Move C to A Until B = Null And C = Null)
A: Null
B: 8, 4 (8 > 6, so move from B to A)
C: 6, 5

A: 8
B: 4
C: 6, 5 (6 > 4, so move from C to A)

A: 6, 8
B: 4
C: 5 (5 > 4, so move from C to A)

A: 5, 6, 8
B: 4 (C = Null, so move from B to A)
C: Null

A: 4, 5, 6, 8 (B = Null and C = Null, so move on to next step)
B: Null
C: Null

Repeat from beginning until A = Null And C = Null. Finish by moving B To A Until B = Null

Honestly, though, to me this is much less clear than what I originally posted.

20

Selection Sort:[list=#][li]Stack A has all cards, stacks B and C are empty.[/li][li]Move first A card to C[/li][li]Compare A and C. If A >= C, move A to B. If A < C, move C to B then move A to C.[/li][li]Repeat step 3 until A is empty.[/li][li]Move first B card to A.[/li][li]Compare B and C. If B >= C, move B to A. If B < C, move C to A then move B to C.[/li][li]Repeat step 6 until B is empty.[/li][li]If A is not empty, start over at step 3.[/li][li]Move entire C stack to A.[/list]Insertion sort:[list=#][]Stack A has all cards, stacks B and C are empty.[/li][li]Move first A card to C.[/li][li]While A < C, move C to B.[/li][li]Move top A to C.[/li][li]Move entire B stack to C.[/li][li]Repeat starting at step 3 until A is empty.[/li][]Move entire C stack to A.[/list]