[Из песочницы] Сортировка очереди без использования дополнительных ресурсов
Недавно столкнулся с такой задачей: «Объединить две очереди таким образом, чтобы суммарная очередь была отсортирована». Причём требование для сортировки такое: не использовать никаких промежуточных объектов, кроме одной переменной, каким бы медленным алгоритм ни был. Первые попытки составить алгоритм сортировки очереди приводили к вопросу о том, как выйти из бесконечного цикла, но в конечном итоге я получил необходимый алгоритм, о котором и пойдёт речь.
Для начала определим реализацию очереди, я сделаю это на языке 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
Результат: очередь отсортирована без использования дополнительных ресурсов.
