a question in stacks

[alex lotel]

i have two stack S1 and S2 the total amount of objects
in them is "n"
in both stack all the objects are sorted in accending order

(the biggest number is on top the smallest number is on the bottom)

and thats the way it goes in both stacks

the question asks me to build a method which
puts all of the objects from stacks S1 and S2 into stack S3
in accended order plus we have to accomplish this using 4n-4 moves ??
(the biggest number is on top the smallest number is on the bottom)

i tried to solve that by
flipping the stacks using the S3 so they will be sorted from the smallest
to the biggest
taking two templorary variables pop each object from each stack
into the temporary variable
and then we compare them and the smallest goes to S3
and the other one waits till we have an object from the other stack which is smaller than him,
and then we have to flip S3 in order have the biggest on top
also i tried using TOP commang but i found out that
its implementation also has push and pop in it.
but in that way we have more than 4n-4 moves
[ February 16, 2008: Message edited by: donaldth smithts ]

[Kaydell Leavitt]

I can see how to do it in 4n moves.

Hint: use a 'merge sort' and move stack1 and stack2 onto stack3. The result of stack3 will be sorted but will be the wrong way, so you could order stack3 by popping off the 2n elements that it contains onto an empty stack.

This is 4n which is Order-n , in "big-Oh" notation, that is O(n).

The minus-four isn't really significant because it's just a constant.
[ February 17, 2008: Message edited by: Kaydell Leavitt ]

[alex lotel]

i cant see how you counted the moves

can you be more spesific on the moves on the stack
like when you say merge sort
merge sort works on an array
we take each on a half of a part from an arraya sort
and then merge again
i dont know how to imagine this on a stacks??

i dont know how its done in order to calculate the number of moves

can you explain you system with more details please?
[ February 17, 2008: Message edited by: donaldth smithts ]

[Henry Wong]

Originally posted by Kaydell Leavitt:
I can see how to do it in 4n moves.

Hint: use a 'merge sort' and move stack1 and stack2 onto stack3. The result of stack3 will be sorted but will be the wrong way, so you could order stack3 by popping off the 2n elements that it contains onto an empty stack.

This is 4n which is Order-n , in "big-Oh" notation, that is O(n).

The minus-four isn't really significant because it's just a constant.

The minus four is significant because it is not a problem with Big O -- the problem states that you must do it in 4n-4 moves. It is a worst case limitation on the moves, which must be honored.

Yes, you can do it in 4n moves. The merge sort will be the first n moves. The move from S3 to either s1/s2 will be the second n moves. The move from s1/s2 to s2/s1 will be the third n moves. And finally, the move from s2/s1 back onto s3 will be the final n moves.

Now how do you get the 4 moves back? You can get it back by consolidating the phases. For example, you can save one move between the third n and forth n moves. This is the easy one to envision -- the other three are a bit harder to find... which I will leave for everyone to try to find first...

Henry

[alex lotel]

how do i do merge sort on stacks??

[Kaydell Leavitt]

I just looked up "merge sort" in wikipedia.org and I must have used the wrong terminology.

What I meant was:

1. Create a new stack, called stack4
2. loop as long as stack1 or stack2 has objects on them
3. compare the object on the top of stack1 to the object that is on the top of stack2
4. pop the larger object off of its stack and push it onto stack4
5. end of loop // you loop until both stack1 and stack2 are empty

// At this point all 2n objects are on stack4 in descending order.
// We now need to reverse the objects

1. Create a new stack, called stack3
2. loop until stack4 is empty
3. pop the top object off of stack4 and push it onto stack3
4. end of loop // the loop ends when stack4 is empty.

// At this point, stack3 has all 2n objects in ascending order

// How many moves did it take? 4n. I'll leave it to you to do it in less than 4n moves.
// but as long as we're optimizing the code, what if instead of using a stack for stack4,
// we used a Queue. Then we wouldn't have to reverse stack4. The Queue would
// already be in the correct order after 2n moves (but I guess this isn't what was specified).
// Does the specification require that we only use Stack objects?

Kaydell
[ February 18, 2008: Message edited by: Kaydell Leavitt ]

[alex lotel]

the total number of objects in both stacks is "n" (not 2n)

does that changes your answer somehow??

because i was spesificly asked 4n-4

[Henry Wong]

I just looked up "merge sort" in wikipedia.org and I must have used the wrong terminology.

A merge sort works with arrays. A merge sort is recursive. Blah. Blah. Blah. Both stacks are already sorted -- so when you said "merge sort", I just thought you meant "merge" the two stacks together... Which from your description, I understood correctly.

1. Create a new stack, called stack4
2. loop as long as stack1 or stack2 has objects on them

No... the total amount of items is n. If you create a forth stack, you can do the whole thing in 2n. This is why I assumed a forth stack is not allowed -- and that it must be solved within the three allocated stacks.

Henry

[alex lotel]

so is there a way to solve it with 3 stacks??
4n-4 moves

[Henry Wong]

Originally posted by donaldth smithts:
so is there a way to solve it with 3 stacks??
4n-4 moves

Sure... and in an eariler post, I gave you a hint on how to do it. Take a shot at figuring it out. It's not that hard.

Henry

[alex lotel]

move bank:
push =1 move
pop =1 move
top =2 moves (because its implemented using i pop and one push command)

1)we look at the values of each two top object from stack S1 and S2
and push the smallest to S3
in this step we make the Top command n times
we make the pop command n times and we make the push command n times
thats makes us 2n+n+n =4n

2)now we need to flip S3 but we already got an overdraw in our bank account
and IRS is knocking on my door righ now

you said
"you can save one move between the third n and forth n moves. This is the easy one to envision -- the other three are a bit harder to find... which I will leave for everyone to try to find first... "

i dont know how to make that any simpler
i thought of it many time
???

[Henry Wong]

move bank:
push =1 move
pop =1 move
top =2 moves (because its implemented using i pop and one push command)

Ohh... My definition of a move as an item being moved from one stack to another.

If you define this as two moves. And to even look at the top of the stack as two moves.... then you're done. With your definition, I don't believe the problem can be solved.

Henry
[ February 18, 2008: Message edited by: Henry Wong ]

[alex lotel]

so by your definition how whould you solve it??

[Henry Wong]

Originally posted by donaldth smithts:
so by your definition how whould you solve it??

First of all, you need to confirm the rules first. Your homework assignment can't be done if you don't know what you are supposed to do.


Second of all, it is still a homework assignment. And based on my definition, I did most of it for you in a previous post (more than I would like actually).

On the chance that my definition is the correct one, it is against JavaRanch best-practices to give you the answer without you trying it yourself. See...

http://faq.javaranch.com/java/DoYourOwnHomework

Henry

[alex lotel]

in my threades i showed some ways
in which i tried to solve it


in your first thread you sayd that there is some way to save moves
between the 4th and the 5th step
and you will live that to me

thats not helping me
i need your full solution
[ February 18, 2008: Message edited by: donaldth smithts ]

[alex lotel]

you are right the question says
that it counts the moves from one stack to another

can you tell me the full theoretical solution??
[ February 18, 2008: Message edited by: donaldth smithts ]

[alex lotel]

(we count only moves from one stack to the other)
i flipped the stacks and compared each pare of Top objects
and pushed the smallest

i got to 4n moves

where can i get this -4 shortcut???