Для начала определим реализацию очереди, я сделаю это на языке 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
Результат: очередь отсортирована без использования дополнительных ресурсов.
Комментарии (23)
time2rfc
28.03.2016 18:311) сортируете одну очередь руками с использование свободной переменной
2) сортируете вторую очередь руками с использование свободной переменной
3) делаете слияние двух очередей
dyadyaSerezha
28.03.2016 20:54Именно. Хоть руками, хоть ногами, хоть с использованием любой библиотечной функции. Алгоритмов вагон и тележка, и почти все не требуют доп.мамяти (то есть, О(1)). В чем проблема-то?
Mrrl
29.03.2016 08:45Есть разница между использованием О(1) и использованием ровно одной переменной. Мы, например, не можем переложить начало очереди в конец, не испортив какого-нибудь счётчика (если он зачем-то нужен).
ndkoval
28.03.2016 18:31Недавно столкнулся с такой задачей: «Объединить две очереди таким образом, чтобы суммарная очередь была отсортирована».
Мне кажется или статья о другом
Как отсортировать очередь используя O(1) дополнительной памяти:
На каждом шаге:
Нашли максимум в очереди за O(N) (пробегаем по очереди, пропуская элементы, добавленные в п.3, всегда знаем сколько их на текущем шаге)
Удалили этот максимум из очереди за O(N) (пробегаем по очереди, пропуская элементы, добавленные в п.3, всегда знаем сколько их на текущем шаге)
Добавили его в конец очереди
Делаем N таких шагов. Итого, отсортировали за O(N^2) с доп. памятью O(1)
Остался один вопрос: что значит «пробегаем по очереди». В качестве ответа псевдокод ниже
for i = 1..q.size()
tmp = q.pop()
// do something with element
q.push(tmp)
После исполнения данного кода получаем такое же состояние очереди, как и до исполнения.
Videoman
28.03.2016 18:32+1Для этой задачи есть уже давно было придумано более изящное, на мой взгляд решение. Стандартная реализация очереди с приоритетом (ваш случай когда весами элементов являются сами элементы) отлично реализуется на структуре heap, где элементы хранятся в сплошном массиве и каждый новый элемент становится в свою позицию простыми обменами не более чем за O(log N). Собственно всем известный heapsort как раз так и реализован. Для слияния нужно просто одну очередь по-поэлементно влить в другую.
Zealint
28.03.2016 19:35+1Действительно, я тоже не понял, зачем заниматься ерундой, когда очередь с приоритетами (как идея) существует не один десяток лет. С другой стороны, в силу некорректности формулировки задания, нельзя точно сказать, с каких данных мы начинаем и что считать дополнительной памятью. На месте исполнителя я требовал бы более чёткой формулировки (что именно дано и в каком виде оно перед нами изначально). Потому что если очереди уже даны в некотором виде (например, в виде списков), то я не вижу каких-то способов использовать heap без нарушения правила одной переменной, тогда придётся извращаться. Если данные даны абстрактно, то можем считать, что они даны в массиве. Дальше всё зависит от того, в одном они массиве или в двух...
Короче, обычно когда задачу формулируют именно так, я возвращаю её автору со словами "сам решай", потому что так задачи не ставятся, когда от трактовки формулировки зависит метод решения.
Кроме того, неплохо было бы понимать, для чего вообще даются подобные задачи. Одно дело для разминки, а другое, когда есть реальная необходимость экономить память. В первом случае это может представлять интерес, конечно, а во втором случае память нужно начинать экономить, например, тем, что не писать сообщения типа "queue is full!", не писать на Python и всё-таки хранить данные иначе.
codeAXE
28.03.2016 22:59Опасная конструкция:
def get_list(self):
return self.queue
Отдаете ссылку на приватный атрибут, т.е. можно изменять очередь вне класса
лучше так сделать:
return list(self.queue)
michael_vostrikov
29.03.2016 07:33Причём требование для сортировки такое: не использовать никаких промежуточных объектов, кроме одной переменной, каким бы медленным алгоритм ни был.
Так ведь steps это вторая переменная. Получается, это требование нарушено?Mrrl
29.03.2016 09:44Получается, что так. Либо можно что-нибудь посчитать, либо запомнить (или переставить) элементы в очереди — но не одновременно.
С другой стороны, ничто не запрещает нам добавить новый пустой элемент в очередь и использовать его для сортировки пузырьком?
SerjihSklovski
29.03.2016 12:19Нет, ну переменные счётчика использовать можно. Главное не использовать дополнительных очередей, списков, массивов — таких вот объектов. То есть только одну промежуточную переменную можно использовать, но не больше.
Mrrl
29.03.2016 10:28Без счётчиков, но с дополнительным пустым элементом в очереди:
queue.Push(new Item()); for(;;){ for(;;){ temp=queue.Pop(); if(queue.Get()==Item.Empty) goto _1; if(queue.Get()<=temp) break; queue.Push(temp); } for(;;){ if(queue.Get()==Item.Empty){ queue.Push(temp); queue.Push(queue.Pop()); break; } if(queue.Get()<temp) queue.Push(queue.Pop()); else{ queue.Push(temp); temp=queue.Pop(); } } } _1: queue.Pop();
nikotin77
29.03.2016 12:08Почему бы не сделать проще:
Слить две очереди в одну.
Отсортировать с учетом требований.SerjihSklovski
29.03.2016 12:14Дело в том, что слияние очередей не так важно, как их сортировка. Сложность задачи заключалась именно в разработке алгоритма сортировки, который я и привёл.
nickolaym
29.03.2016 16:45На питоне можно было проще — на голых списках без создания собственного класса. list.append(x) и list.pop(0)
Ну и более чистый (имхо) код выглядит так
def sort(q): n = len(q) for k in range(1,n): # start with 1, because 1 item is always sorted # n-k items not sorted yet, then k items sorted x = pop(q) # n-k-1 not sorted yet, k sorted for i in range(n-k-1): roll(q) # k sorted, n-k-1 not yet pushed = False for i in range(k): y = pop(q) if not pushed and x < y: push(q, x) pushed = True push(q, y) if not pushed: push(q, x) # k+1 sorted (including x), n-k-1 not yet
А можно и не вставками, а обменами
def sort(q): n = len(q) if n < 2: return retry = True while retry: retry = False x = pop(q) for i in range(n-1): y = pop(q) if x <= y: push(q, x) x = y else: push(q, y) retry = True # reordered push(q, x)
4eyes
Похоже, что вы изобрели Selection Sort.
4eyes
Допишу вдогонку.
Попробуйте еще глянуть такие вещи, как:
И если уж совсем заморочиться, то есть in-place bottom-up quicksort, которая обычно еще быстрее, но имеет ряд неочевидных подводных камней вроде деградации до O(N^2) на неудачных наборах данных. Впрочем, все подводные камни обходятся.
Всё это будет стоить вам O(1) по памяти.
qw1
qsort разве не потребует log(N) памяти под стек вызовов или для хранения маркеров разбиений массива?
4eyes
Я ошибся, спасибо. Действительно, придется хранить разбиения, по памяти выйдет log N. И к тому же, я спутал его с bottom-up mergesort с еще большей сложностью по памяти.
Наверное, heap sort идеальный выбор.