Сортировка очереди без использования дополнительных ресурсов

Недавно столкнулся с такой задачей: «Объединить две очереди таким образом, чтобы суммарная очередь была отсортирована». Причём требование для сортировки такое: не использовать никаких промежуточных объектов, кроме одной переменной, каким бы медленным алгоритм ни был. Первые попытки составить алгоритм сортировки очереди приводили к вопросу о том, как выйти из бесконечного цикла, но в конечном итоге я получил необходимый алгоритм, о котором и пойдёт речь.

Для начала определим реализацию очереди, я сделаю это на языке Python, используя стандартные списки:

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

Набор методов самый стандартный. Очередь может быть фиксированного размера, тогда в конструктор нужно передать числовой параметр, определяющий размер, в противном случае очередь получится бесконечной. Метод get_list() небезопасный, поскольку возвращает ссылку на внутренний список, и изменение его извне совершенно не рекомендуется. Но для отладки он может пригодиться.

За контроль пустоты/полноты очереди отвечают классы исключений EmptyQueueError и FullEmptyError соответственно.

Ну а теперь приступим к самому интересному — сортировке очереди. Сортировка происходит от наименьшего элемента к большему. Мы имеем возможность использовать одну переменную для временного хранения элемента из очереди. Также в нашем распоряжении есть метод get_head(), который просто возвращает элемент из головы очереди. Основа алгоритма сортировки состоит в том, что мы помещаем в переменную temp очередной элемент, используя метод pop(). Далее в цикле мы будем сравнивать голову очереди с этим temp, и если головной элемент окажется больше, то помещаем temp в конец очереди, а потом присваиваем ему следующий элемент из головы (pop()). Если же головной элемент окажется не больше, то помещаем его в хвост, а temp не трогаем, то есть делаем «перемотку» очереди на один элемент.

Но вопрос: когда цикл следует остановить?

Когда алгоритм находит максимум, необходимо промотать очередь полностью, чтобы удостовериться, что в очереди нет большего значения. Значит, промотка должна выполняться столько раз, сколько элементов находится в очереди. Для этого нужна переменная счётчика (steps). После промотки можно смело затолкнуть в очередь temp, и повторить операцию.

А в случае нахождение нового максимума в очереди сбрасываем счётчик промотки в 0.

Так что сначала полагаем steps = 0, и если следующий максимум не обнаружен, увеличиваем на 1.

Но так как после выполнения этого цикла очередь вряд ли отсортируется, необходимо повторить операцию столько раз, сколько элементов в очереди без одного, то есть длина_очереди — 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

Результат: очередь отсортирована без использования дополнительных ресурсов.