Coding challenge – Sorting a queue with another queue2 min read

Question: Given a queue of integers and the goal is to sort the integers in the queue by using another queue (extra space with the same size as the given queue)

Breakdown:

1. We got an extra queue here that we can make use of it for our algorithm. Let’s use the extra queue to hold only sorted values.
2. So, if an element which is polled/dequeued from the queue (front element) is less than the element which we just enqueued in the extra queue, then above statement step 1 is broken, so we just poll/dequeue the front element from the queue and add it back to the same queue.
3. Once all the elements in the queue are processed by using the above two steps, then we dequeue all sorted elements from the extra queue and add them back to the original queue.
4. The queue is not sorted until the given queue and the extra queue is not equal in size. So we do start from step 1 and repeat the algorithm.

Let’s put these steps into action:

package com.zingscoop.challenges.SearchAndSorting;

import java.util.ArrayDeque;
import java.util.Queue;

public class SortQueueUsingExtraQueue {

    static void sort(Queue<Integer> queue) {

        // Additional Queue
        Queue<Integer> extraQueue = new ArrayDeque<>();

        int sizeTracker = 0;

        int queueSize = queue.size();
        int lastElement = queue.peek();

        boolean isSorted = false;

        while(!isSorted) {

            if(lastElement <= queue.peek()) {
                //Step 1
                lastElement = queue.poll();
                extraQueue.add(lastElement);
            } else {
                // step 2 
                queue.add(queue.poll());
            }
            
            System.out.println("Sorted queue so far: " + extraQueue);

            ++sizeTracker;

            //Keep repeating step 1 and step 2 until all elements are processed
            if(sizeTracker != queueSize) continue;

            // we are done, if we simply have all the elements in the extra queue (already sorted)
            if(queueSize == extraQueue.size()) isSorted = true;

            System.out.println("Enquing all sorted element into original queue");

            //Step 3
            while(extraQueue.size() > 0) {
                queue.add(extraQueue.poll());
                lastElement = queue.peek();
            }

            //Step 4 - Reset and start from step 1
            sizeTracker = 0;
        }

    }
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();

        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(1);
        queue.add(5);
 
        System.out.println("Queue before sorting : " + queue);
        sort(queue);
        System.out.println("Queue after sorting  " + queue);
    }
}

The output will be as below

Queue before sorting : [2, 3, 4, 1, 5]
Sorted queue so far: [2]
Sorted queue so far: [2, 3]
Sorted queue so far: [2, 3, 4]
Sorted queue so far: [2, 3, 4]
Sorted queue so far: [2, 3, 4, 5]
Enquing all sorted element into original queue
Sorted queue so far: [1]
Sorted queue so far: [1, 2]
Sorted queue so far: [1, 2, 3]
Sorted queue so far: [1, 2, 3, 4]
Sorted queue so far: [1, 2, 3, 4, 5]
Enquing all sorted element into original queue
Queue after sorting  [1, 2, 3, 4, 5]

As we can see in the output console, the final queue is sorted.

All the above examples are available on github.

Stay subscribed. more to come in this space. Happy Scooping… Leave a comment if you got any challenges that need to be solved.