Sorting a queue using same queue
Sort(Q,n):
for i = 0 to n-1
min = findMin(Q, n-i, 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)
Ascending sort, runs in O(n^2) time, in space O(1) (i.e. the queue is O(n) space, and extra space required by the algorithm is O(1))
Explanation:
Essentially, we iterate through the queue n times, each time the iteration costs 2n.
On each iteration, we go through the entire queue and pick the minimum within the relevant number of items. So at first the relevant number of items is n, since we want the minimum of them all. The next iteration we want the minimum of the first n-1 items, and then n-2 items, etc. Since the algorithm will stack these minimums at the end.
Once we found the minimum, we need to iterate over the whole stack again in order to snatch it and stack it on the end.
The main idea here, is that a dequeue followed by an enqueue of that same element will allow us to iterate over the queue and check minimum/maximum while preserving order.
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
end
end
enqueue x
end