Sorting a queue without using additional resources

I recently encountered the following problem: “Combine two queues in such a way that the total queue is sorted.” And the requirement for sorting is this: do not use any intermediate objects, except for one variable, no matter how slow the algorithm may be. The first attempts to compose a queue sorting algorithm led to the question of how to get out of an infinite loop, but in the end I got the necessary algorithm, which will be discussed.

First, let's define the implementation of the queue, I will do it in Python using standard lists:

class EmptyQueueError(Exception):
    @staticmethod
    def message():
        return 'queue is empty!'
class FullQueueError(Exception):
    @staticmethod
    def message():
        return 'queue is full!'
class Queue:
    def __init__(self, max_size=None):
        self.__queue = []
        self.__max_size = max_size
    def get_size(self):
        return len(self.__queue)
    def get_list(self):
        return self.__queue
    def push(self, item):
        if len(self.__queue) != self.__max_size or self.__max_size is None:
            self.__queue.append(item)
        else:
            raise FullQueueError
    def pop(self):
        if len(self.__queue):
            item = self.__queue[0]
            del self.__queue[0]
            return item
        else:
            raise EmptyQueueError
    def get_head(self):
        if len(self.__queue):
            return self.__queue[0]
        else:
            raise EmptyQueueError

The set of methods is the most standard. The queue can be of a fixed size, then in the constructor you need to pass a numerical parameter that determines the size, otherwise the queue will be infinite. The get_list () method is unsafe because it returns a link to the internal list, and changing it from the outside is completely not recommended. But it can come in handy for debugging.

The EmptyQueueError and FullEmptyError exception classes are responsible for controlling the emptiness / completeness of the queue, respectively.

Well, now let's get to the fun part: sorting the queue. Sorting occurs from the smallest item to the largest. We are able to use one variable to temporarily store an item from the queue. We also have a method at our disposal.get_head () , which simply returns the item from the head of the queue. The basis of the sorting algorithm is that we put the next element in the temp variable using the pop () method . Further in the loop we will compare the head of the queue with this temp , and if the head element is larger, then put temp at the end of the queue, and then assign it the next element from the head ( pop () ). If the head element is no more, then we put it in the tail, and do not touch temp , that is, we do “rewind” the queue to one element.

But the question is: when should the cycle be stopped?

When the algorithm finds the maximum, it is necessary to scroll the queue completely to make sure that there is no greater value in the queue. So, the winding should be performed as many times as there are elements in the queue. To do this, you need a counter variable ( steps ). After scrolling, you can safely push temp into the queue , and repeat the operation.

And in the case of finding a new maximum in the queue, reset the scroll counter to 0.

So first we set steps = 0 , and if the next maximum is not found, increase by 1.

But since the queue is unlikely to be sorted after completing this cycle, it is necessary to repeat the operation so many times how many elements in the queue without one, that is, queue_length is 1.

def my_sorting(queue):
    for i in range(queue.get_size() - 1):
        temp = queue.pop()
        steps = 0
        while steps < queue.get_size():
            print(temp, queue.get_list())
            if temp < queue.get_head():
                queue.push(temp)
                temp = queue.pop()
                steps = 0
            else:
                queue.push(queue.pop())
                steps += 1
        queue.push(temp)
    print(queue.get_list())
    return queue

Result: the queue is sorted without using additional resources.