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