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 ]

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
Ranch Hand

Joined: Feb 01, 2008
Posts: 191

posted

0

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 ]

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...

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?

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
Ranch Hand

Joined: Feb 01, 2008
Posts: 191

posted

0

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

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
Ranch Hand

Joined: Feb 01, 2008
Posts: 191

posted

0

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 ???

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 ]

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...