Sort a queue using the same queue

Question

I was asked this question, and I think it is doable. However, it is difficult for me to find an algorithm for this. The limitations are that you cannot use any other data structure or create another queue. You can also use enqueue, dequeue and peek (NOT a priority queue).

Thanx for making :)

Answer 1

Sort(Q,n): for i = 0 to n-1 min = findMin(Q, ni, n) reorder(Q, min, n) end for findMin(Q, k, n): min = infinity for i = 1 to n curr = dequeue(Q) if curr < min && i<=k min = curr end if enqueue(Q,curr) end for return min reorder(Q, min, n): for i = 1 to n curr = dequeue(Q) if (curr != min) // I'm assuming that there is a way to differentiate between any two items, this isn't hard to enforce enqueue(Q, curr) end if end for enqueue(Q,min) 

Upward sorting is performed in O (n ^ 2) time, in O (1) space (i.e., the queue is O (n) space, and the additional space required by the algorithm is O (1))

Explanation:

Essentially, we iterate through the queue n times, each time the iteration costs 2n.

At each iteration, we look through the entire queue and select a minimum within the appropriate number of elements. Therefore, first, the corresponding number of elements is n, since we want them to be minimal. In the next iteration, we want the minimum of the first elements n-1, and then n-2 elements, etc. Since the algorithm will add these lows at the end.

Once we have found the minimum, we need to iterate the entire stack again in order to tear it out and put it in the end.

The main idea here is that the dequeue, followed by the enqueue of the same element, will allow us to iterate over the queue and check the minimum / maximum while maintaining order.

Answer 2

BubbleSort using a queue:

 n <- size of queue repeat n times x <- dequeue item repeat (n-1) times y <- dequeue item if x < y then enqueue y else enqueue x x <- y enqueue x