Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we will be discussing 4 different ways to sort a queue. The first approach takes O(n) time and O(n) extra space whereas the second approach takes O(n^2) time and constant extra space (O(1)). We have covered the following techniques to sort a queue:
- Method 1 : Using auxiliary array
- Method 2 : O(1) space required
- Method 3 : Using recursion
- Method 4 : Using stack
Method 1 : Using auxiliary array
We use an auxiliary array to store all the elements of the queue. We then sort the array and put the sorted elements back into the queue.
Algorithm:
The steps to sort a queue using auxiliary array are:
- Create an auxiliary array(static/dynamic).
- Remove all the elements from the queue and put them into the array.
- Sort the array.
- Put elements of the sorted array back into the queue.
Implementation
Java
Queue<Integer> sortQueue(Queue<Integer> q)
{
ArrayList<Integer> temp = new ArrayList<>();
while(q.isEmpty() == false)
{
temp.add(q.peek());
q.pop();
}
Collections.sort(arr);
for(int i=0;i<arr.size();i++)
{
q.add(arr.get(i));
}
return q;
}
CPP
queue<int> Sort_Queue(queue<int> &q)
{
vector<int> temp;
while(!q.empty())
{
temp.push_back(q.pop());
}
sort(temp.begin(),temp.end());
for(int i=0;i<temp.size();i++)
{
q.push(temp.back());
}
return q;
}
Time complexity: O(n * logn)
- Transfering the elements fron the queue to the array requires O(n) time.
- Sorting the array takes O(n * logn).
- Putting the elements back into the queue again takes O(n) time.
Hence, time complexity = O(n) + O(n * logn) + O(n) which can be upper bounded by O(n * logn).
Space complexity : θ(n)
- The auxiliary array contains all the elements of the queue, hence space complexity can be bounded by θ(n) (theta(n)).
Method 2 : O(1) space required
We maintain the sorted queue at the end of the queue. For each of the n iterations, we find the minimum element from the unsorted queue. We store it's value as well as it's index. Then, we remove minIndex - 1 elements from the queue and p insert them back at the end of the queue. We pop the minimum element and store it in a variable. Next, we again remove the elements occuring after the minimum element (elements at indices minIndex+1 to n) and push them at the end f the queue. The detailed algorithm is discusssed below.
Algorithm
The steps to sort a queue using O(1) space are:
Do this N times:
1. Search for the minimum element in the unsorted part of the queue. Store it's value and the index.
2. Remove the elements occuring before the minimum element from the front of the queue and insert them at the end of the queue.
3. Once the index of the minimum element is reached, pop the minimum element ans store it in a variable.
4. Next, remove the elements occuring after the minimum element from the front of the queue and insert them at the end of the queue.
5. Finally, insert the minimum element (from 3) into the end of the queue.
For searching the element in the queue int Step 1, we traverse the queue and find the minimum elemnt. After a complete traversal, the queue comes to the same state as it was before the traversal started. Hence, Step 1 does not effectively change the queue in any way.
Java
Queue<Integer> SortQueue(Queue<Integer> q)
{
int n = q.size();
for(int i=0;i<n;i++) // n iterations for sorting n elements
{
int minIndex = -1;
int minValue = Integer.MAX_VALUE;
for(int j=0;j<n-i;i++) // this loop picks the min elt in the queue
{
if(q.peek() < minValue)
{
minValue = q.peek();
minIndex = j;
}
q.add(q.remove());
}
for(int k=0;k<minIndex;k++) // removes the elements occuring before min elt and adds them at the end of the queue
{
q.add(q.remove());
}
int minElt = q.remove(); // removes the minElt from the queue and stores it for later use
for(int k = minIndex+1;k<n;k++) // removes the elts occuring after minElt from the front of queue and adds them at the queue
{
q.add(q.remove());
}
q.add(minElt); // finally add the minELt at the end of the queue
}
}
CPP
queue<int> sort_queue(queue<int> &q)
{
int n = q.size();
for(int i=0;i<n;i++) // n iterations for sorting n elements
{
int minIndex = -1;
int minValue = INT_MAX;
for(int j=0;j<n-i;i++) // this loop picks the min elt in the queue
{
if(q.front() < minValue)
{
minValue = q.front();
minIndex = j;
}
q.push(q.pop());
}
for(int k=0;k<minIndex;k++) // removes the elements occuring before min elt and adds them at the end of the queue
{
q.push(q.pop());
}
int minElt = q.pop(); // removes the minElt from the queue and stores it for later use
for(int k = minIndex+1;k<n;k++) // removes the elts occuring after minElt from the front of queue and adds them at the queue
{
q.push(q.pop());
}
q.push(minElt); // finally add the minELt at the end of the queue
}
}
Example
Consider a queue Q:
| 5 | 3 | 1 | 2 |
|---|
It needs to be sorted using the above algorithm.
Iteration 1:
- Traverse the queue to find the minIndex and minValue.
minValue = 1,minIndex = 2 - Remove elements from 0 to minIndex-1 (elts at index 0,1)elements and put them at the end.
| 1 | 2 | 5 | 3 |
|---|
- Store the next element in minElt, minElt = 1, and remove it from the queue.
| 2 | 5 | 3 |
|---|
- Remove the elements from minIndex+1 to n-1 (2+1 to 4-1)=> only one element and push it at the end of the queue.
| 5 | 3 | 2 |
|---|
- Insert minElt in the queue
| 5 | 3 | 2 | 1 |
|---|
Iteration 2:
- Step 1 : Traverse to find minIndex = 2,minValue = 2
- Step 2: Remove elts from 0 to 1
| 2 | 1 | 5 | 3 |
|---------:-|---------:|-----------:|-----------:|
- Step 3: minElt = 2, pop the element.
| 1 | 5 | 3 |
|---|
- Step 4 :Remove the remaining elts
| 5 | 3 | 1 |
|---|
- Step 5: Insert minElt
| 5 | 3 | 1 | 2 |
|---|
Iteration 3:
- Step 1: minIndex = 1,minValue = 3.
- Step 2:
| 3 | 1 | 2 | 5 |
|---|
- Step 3: MinElt = 3.
| 1 | 2 | 5 |
|---|
- Step 4:
| 5 | 1 | 2 |
|---|
- Step 5:
| 5 | 1 | 2 | 3 |
|---|
Iteration 4:
- Step 1: minIndex = 0,minValue = 5.
- Step 2: remove elt from Index 0 to -1. Nothing to be removed.
- Step 3: minElt = 5
| 1 | 2 | 3 |
|---|
- Step 4:remove elts from index 0+1 to 4-1
| 1 | 2 | 3 |
|---|
- Insert minElt
| 1 | 2 | 3 | 5 |
|---|
Time Complexity
This algorithm has time complexity of O(n^2)
Space Complexity
Does not use any extra space. So, space complexity is constant or O(1).
Method 3 : Using recursion
We can also use recursion to sort a queue. We first remove the element at the front of the queue. Then, we make a recursive call for the remaining queue. We use recursion in such a way that after the recursive call returns we have a sorted queue in the ascending order (smallest element at the front of the queue). Once this sorted queue is received, we insert our current element we need to place the current elemrnt at it's correct position. To do this, we first pop all the elements which are smaller than the current element and insert then at the end of the queue. Once we find an element equal to or greater than the current element, we insert the current element at the end of the queue. Next, we pop the remaining elements (equal or greater tahn the current element) and insert them at the end of the queue. This will give us a sorted queue.
If you take a closer look at the code implementation given below, you will notice that a variable count is used while popping elements from the queue. This variable plays a very important role in ensuring that the code does not get into an infinite loop in case all elements are smaller than the current element(1st while loop) and when all elements are greater or equal to the current eleemnet(2nd while loop).
To gain more clarity on this aspect, consider that our current element is the greatest element of the queue and we need to place it at it's correct position. The condition in the while loop says that we keep on pushing the popped elements of the queue till q.peek() < x i.e the element at the front of the queue is smaller than the current element. This will always be true if the current element is the greatest element which is the case. Hence if we had not put the condition count < n, we would have kept on traversing the queue in search of a greater/ equal element which did not exist in the queue. The condition count < n ensures that we stop the loop if we have traversed the entire queue once.
A similar logic is used in the second while loop where we pop elements until we find an element smaller than the current element. The conditon says q.peek() >= x (element at the front is greater than/equal to the cy=urrent element). This will always be true if the cureent elemnt is the smallest of all elements. Hence, count < n makes sure that we stop after one complete traversal of the queue even when the primary condition is always true.
Algorithm
The steps to sort a queue using recursion are:
- If the q has no element or has only 1 element, return.
- Pop the current element present at the front of the queue.
- Now, use recursion to sort the remaining queue.
- The recursive call returns a sorted queue (in ascending order), which does not contain the current element.
- We pop the elements smaller than the current element, and insert them at the end of the queue.
- Once we encounter an element greater or equal to the current element at the front of the queue, we push the current element at the end of the queue.
- Now, pop the elements greater than/equal to the current element and insert them at the end of the queue until an element smaller than the current element is found.
Java
public static void sortQueue(Queue<Integer> q)
{
if(q.size() == 0 || q.size() == 1)
return;
int n = q.size();
int count = 0;
int x = q.poll();
sortQueue(q); // returns sorted queue
while(q.peek() < x && count < n) // while elements are smaller than the curr elt, pop them and insert them at the end
{
q.add(q.poll());
count++;
}
q.add(x); // once an elt greater of equal is found at the front of the queue, insert the curr elt
if(count == n) // if curr elt is the greatest, we return at this point
return;
count = 0;
while(q.peek() >= x && count<n) // now we push all the elts greater than the curr elts at the end of the queue
{
q.add(q.poll());
count++;
}
}
CPP
void sort_queue(queue<int> &q)
{
if(q.size() == 0 || q.size() == 1)
return;
int n = q.size();
int count = 0;
int x = q.pop();
sortQueue(q); // returns sorted queue
while(q.peek() < x && count < n) // while elements are smaller than the curr elt, pop them and insert them at the end
{
q.push(q.pop();
count++;
}
q.push(x); // once an elt greater of equal is found at the front of the queue, insert the curr elt
if(count == n) // if curr elt is the greatest, we return at this point
return;
count = 0;
while(q.front() >= x && count<n) // now we push all the elts greater than the curr elts at the end of the queue
{
q.push(q.pop());
count++;
}
}
Time complexity
For inserting every element at its correct position, we would require O(n) time. Hence for n elements, this algortihm takes O(n^2) time.
Space Complexity
This algorithm does not require any extra space except the function call stack. The functioncall stack itself can take upto O(n) space when we are processing the first item of the queue.
Method 4 : Using stack
Idea is to maintain the sorted elemnts of the queue in the auxiliary stack. We also use an extra queue for maintaining the order of the sorted elemnts in the stack when a new element is to be pushed in the stack.
Algorithm
The steps to sort a queue using Stack are:
- Create an auxiliary stack and an auxiliary queue.
- If the stack is empty, push the element in the stack.
- If the next element at the front of the queue is greater than the top of the stack, push it on the stack.
- Else, pop the elements out of the stack until a smaller or equal elemnet is found at the top of the stack.
- The popped elements in step 4, must be pushed into the auxiliary queue and once a smaller/equal element is found, push the current element and empty the auxiliary queue on the stack.
- Continue until the stack size becomes equal to the size of the input queue and he input queue becomes empty.
- Now transfer all the elements from the stack to the queue. The resulting queue will have the elements in descending order.
With this, you must have a strong idea of sorting a queue.
