Merge Sorted Stacks in Ascending Order Using 4n-4 Moves

  • Thread starter Thread starter transgalactic
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the problem of merging two sorted stacks, S1 and S2, into a third stack, S3, while maintaining ascending order and adhering to a constraint of using 4n-4 moves. Participants explore various methods and strategies to achieve this goal, including considerations of move efficiency and stack manipulation techniques.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant describes an initial approach involving flipping stacks and using temporary variables to compare and sort elements, but notes concerns about exceeding the move limit.
  • Another participant suggests that the problem resembles the Tower of Hanoi, implying a potential strategy based on that framework.
  • A different participant proposes a series of moves to exchange stacks and reverse their order, indicating that this could be done in 3n/2 moves, but does not clarify how this relates to the original problem constraints.
  • One participant critiques the initial approach, pointing out that flipping stacks incurs too many operations and suggests building the temporary stack in reverse order to save moves.
  • There is a suggestion to optimize the process by directly placing elements from temporary variables into their correct positions in S3, rather than using a temporary stack for all elements.
  • Participants mention the concept of invariants as a potential aid in solving the problem, though the specifics of this application are not fully explored.

Areas of Agreement / Disagreement

Participants express differing views on the efficiency of various methods proposed for merging the stacks. There is no consensus on a single approach, and multiple competing strategies are presented, indicating that the discussion remains unresolved.

Contextual Notes

Participants highlight limitations in their approaches, including the need to consider the number of operations required for each method and the implications of stack order on the overall move count. Some assumptions about the operations and their costs are not fully detailed.

transgalactic
Messages
1,386
Reaction score
0
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 that's 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
 
Technology news on Phys.org
This is the http://en.wikipedia.org/wiki/Tower_of_Hanoi" Problem if I am not mistaken. This should get you started.
 
Last edited by a moderator:
a. Move S1 to S3 = S1'
b. Move S2 to S1 = S2'.
c. Move S3 to S2 = S1.
*the two stacks are exchanged and (their) one order reversed in 3n/2 moves.
d. now you can continue.

hint: repeat a.b,c to have 6n/2 moves.
 
Last edited:
transgalactic said:
i tried to solve that by
flipping the stacks using the S3 so they will be sorted from the smallest
to the biggest
This along requires 2n operations. Not a good start. Not only that, you will have to reverse the temporary stack at the end, costing another 2n operations. You have already exceeded the budget with this approach and you haven't even started building the temporary stack. Solution: build the temporary stack in reverse order.
and then we compare them and the smallest goes to S3
You don't have to do this to the bitter end. You can save some operations by avoiding putting all of the elements on the temporary stack. At some point you will have emptied both stacks, leaving you with two elements in the temporary variables and n-2 elements in the temporary stack. Why not put the two temporary variables directly where they belong instead?

It helps to think of invariants, if you have been taught that concept.
 

Similar threads

Solving MIPS Runtime Error: Address Out of Range 0x00000000
  • · Replies 1 ·
Replies
1
Views
11K
Don't understand tower of Hanoi Program Stack
  • · Replies 5 ·
Replies
5
Views
2K
Where is an ISR stored? Estimated time taken to address an interrupt
  • · Replies 6 ·
Replies
6
Views
4K
MHB Verifying Sequence of Push/Pop Ops in a Stack
  • · Replies 2 ·
Replies
2
Views
2K
Stacking rings on fingers by decreasing stack size (permutations)
  • · Replies 1 ·
Replies
1
Views
1K
MHB How to Efficiently Merge a Sorted List and a Pre-Order Sorted Tree?
  • · Replies 1 ·
Replies
1
Views
2K
MIPS Help (converting numbers to diff bases)
  • · Replies 5 ·
Replies
5
Views
10K
Merge sort using linked indexes
  • · Replies 1 ·
Replies
1
Views
2K
Troubleshooting Quicksort: Stack Overflow and Random Pivots
  • · Replies 7 ·
Replies
7
Views
13K
Double Pendulum in C (Trace Motion Real-Time + gif output)?
  • · Replies 2 ·
Replies
2
Views
4K