Sorting Queue Without Extra Space

Last Updated on November 27, 2023 by Ankit Kochar

Sorting a queue without utilizing extra space presents an intriguing challenge in computer science. Queues, a fundamental data structure, follow the FIFO (First-In-First-Out) principle, making their sorting a complex task without additional storage. Unlike arrays or lists, queues lack direct access to elements beyond the front, complicating traditional sorting algorithms’ implementation.

In this article, we delve into the fascinating realm of sorting queues without the luxury of additional space. We explore various efficient algorithms and strategies that enable us to rearrange the elements within a queue to adhere to a sorted order while adhering to the constraints of space efficiency.

Given below are the operations of the queue:

• Enqueue: This function is used to add an element to the rear end of the queue. If the queue is completely filled, then it will be in an overflow condition. The time complexity of the enqueue is O(1).
• Dequeue: This function is used to remove an element from the front end of the queue. If the queue is empty, then it will be in an underflow condition. The time complexity of the dequeue is O(1).
• Front: This function returns the front element of the queue. The time complexity of this function is O(1).
• Rear: This function returns the last element of the queue. The time complexity of this function is O(1).

And we have C++ STL operations also such as isEmpty(): This operation is used to check whether the queue is empty or not.

Let’s take an example:
Input queue 1 = 100 50 40 200
MODIFIED QUEUE
Output queue = 40 50 100 200

Input queue 2 = 4 5 1 3 2
MODIFIED QUEUE
Output queue 2 = 1 2 3 4 5

What if we are allowed to use extra space?

If we are allowed to use an extra space we’ll use an array and move all the elements from the queue to array and then sort the array and finally move all the elements back to the queue.

How to do it without using an extra space?

So, on every iteration on the queue, we’ll be looking for the next minimum index. To do this we dequeue the element then we enqueue the element until we will find the next minimum. Basically in this operation the queue is not changed at all and after we have found the minimum index then we dequeue and enqueue the elements from the queue except for the minimum index. After the traversal of the queue we’ll insert the minimum from the rear of the queue. We keep on this until all minimums are pushed to the front and finally the queue will become sorted.
We repeat this method for n times.
And also first we need to find the maximum, because on every iteration we need to find the next minimum so that we can compare it with the maximum element from the queue.

#include <bits/stdc++.h>
using namespace std;

int minIndex(queue<int> &q, int sortedIndex)
{
	int min_index = -1;
	int min_val = INT_MAX;
	int n = q.size();
	for (int i=0; i<n; i++)
	{
		int curr = q.front();
		q.pop(); 

		
		if (curr <= min_val && i <= sortedIndex)
		{
			min_index = i;
			min_val = curr;
		}
		q.push(curr); 
	}
	return min_index;
}

void insertMinToRear(queue<int> &q, int min_index)
{
	int min_val;
	int n = q.size();
	for (int i = 0; i < n; i++)
	{
		int curr = q.front();
		q.pop();
		if (i != min_index)
			q.push(curr);
		else
			min_val = curr;
	}
	q.push(min_val);
}

void sortQueue(queue<int> &q)
{
	for (int i = 1; i <= q.size(); i++)
	{
		int min_index = minIndex(q, q.size() - i);
		insertMinToRear(q, min_index);
	}
}

int main()
{
queue<int> q;
q.push(300);
q.push(110);
q.push(150);
q.push(40);

sortQueue(q);

while (q.empty() == false)
{
	cout << q.front() << " ";
	q.pop();
}
cout << endl;
return 0;
}

import java.util.LinkedList;
import java.util.Queue;
class GFG
{

	public static int minIndex(Queue<Integer> list,
									int sortIndex)
	{
	int min_index = -1;
	int min_value = Integer.MAX_VALUE;
	int s = list.size();
	for (int i = 0; i < s; i++)
	{
		int current = list.peek();
		
	
		list.poll();

		if (current <= min_value && i <= sortIndex)
		{
			min_index = i;
			min_value = current;
		}
		list.add(current);
	}
	return min_index;
}

	public static void insertMinToRear(Queue<Integer> list,
											int min_index)
	{
		int min_value = 0;
		int s = list.size();
		for (int i = 0; i < s; i++)
		{
		int current = list.peek();
		list.poll();
		if (i != min_index)
			list.add(current);
		else
			min_value = current;
		}
		list.add(min_value);
	}
	
	public static void sortQueue(Queue<Integer> list)
	{
		for(int i = 1; i <= list.size(); i++)
		{
			int min_index = minIndex(list,list.size() - i);
			insertMinToRear(list, min_index);
		}
	}

	public static void main (String[] args)
	{
		Queue<Integer> list = new LinkedList<Integer>();
		list.add(300);
		list.add(110);
		list.add(150);
		list.add(40);
		
		sortQueue(list);
		
		while(list.isEmpty()== false)
		{
			System.out.print(list.peek() + " ");
			list.poll();
		}
	}
}

from queue import Queue

def minIndex(q, sortedIndex):
	min_index = -1
	min_val = 999999999999
	n = q.qsize()
	for i in range(n):
		curr = q.queue[0]
		q.get() 
		if (curr <= min_val and i <= sortedIndex):
			min_index = i
			min_val = curr
		q.put(curr) 
	return min_index

def insertMinToRear(q, min_index):
	min_val = None
	n = q.qsize()
	for i in range(n):
		curr = q.queue[0]
		q.get()
		if (i != min_index):
			q.put(curr)
		else:
			min_val = curr
	q.put(min_val)

def sortQueue(q):
	for i in range(1, q.qsize() + 1):
		min_index = minIndex(q, q.qsize() - i)
		insertMinToRear(q, min_index)

if __name__ == '__main__':
	q = Queue()
	q.put(300)
	q.put(110)
	q.put(150)
	q.put(40)
	
	sortQueue(q)
	
	while (q.empty() == False):
		print(q.queue[0], end = " ")
		q.get()

Conclusion
Sorting a queue without extra space challenges our understanding of data structures and algorithms. Through innovative strategies like recursion, the two-queue approach, or leveraging priority queues or heaps, we can achieve a sorted queue while adhering to space constraints.

While each method has its advantages and complexities, understanding these techniques expands our problem-solving abilities and enriches our grasp of fundamental computer science principles.

In conclusion, the quest to sort a queue without extra space not only fosters creativity but also underscores the versatility and adaptability of algorithms in managing constrained environments.

Frequently Asked Questions (FAQ) Related to Sorting Queue Without Extra Space

Here are some FAQs related to Sorting Queue Without Extra Space.

1. Why is sorting a queue without extra space challenging?
Queues follow the FIFO principle and lack direct access to elements beyond the front. Traditional sorting algorithms often rely on extra space or random access to elements, making it challenging to apply them directly to queues without additional storage.

2. What are the advantages of sorting a queue without extra space?
Sorting a queue without extra space showcases efficient algorithm design, minimizing memory usage, and enhancing computational efficiency. It also deepens understanding and utilization of fundamental data structures and algorithms.

3. Which method is the most efficient for sorting a queue without extra space?
The efficiency of methods varies based on various factors such as the size of the queue, the complexity of the algorithm, and the specific constraints. Each method, like recursion, two-queue approach, or priority queues, has its trade-offs in terms of time and space complexity.

4. Can these sorting techniques be applied to other data structures?
While these techniques are tailored for queues, variations or adaptations can be explored to sort elements in other data structures like stacks or specific types of linked lists. However, the direct application may require adjustments due to structural differences.