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

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

Для начала определим реализацию очереди, я сделаю это на языке 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

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

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 23

    0
    Похоже, что вы изобрели Selection Sort.
      0
      Допишу вдогонку.
      Попробуйте еще глянуть такие вещи, как:
      • Insertion Sort с O(1) на уже отсортированных данных
      • Heap Sort c гарантированным O(n log n).

      И если уж совсем заморочиться, то есть in-place bottom-up quicksort, которая обычно еще быстрее, но имеет ряд неочевидных подводных камней вроде деградации до O(N^2) на неудачных наборах данных. Впрочем, все подводные камни обходятся.
      Всё это будет стоить вам O(1) по памяти.
        0
        И если уж совсем заморочиться, то есть in-place bottom-up quicksort, которая обычно еще быстрее

        qsort разве не потребует log(N) памяти под стек вызовов или для хранения маркеров разбиений массива?
          0
          Я ошибся, спасибо. Действительно, придется хранить разбиения, по памяти выйдет log N. И к тому же, я спутал его с bottom-up mergesort с еще большей сложностью по памяти.
          Наверное, heap sort идеальный выбор.
      0
      1) сортируете одну очередь руками с использование свободной переменной
      2) сортируете вторую очередь руками с использование свободной переменной
      3) делаете слияние двух очередей
        0
        Именно. Хоть руками, хоть ногами, хоть с использованием любой библиотечной функции. Алгоритмов вагон и тележка, и почти все не требуют доп.мамяти (то есть, О(1)). В чем проблема-то?
          0
          Есть разница между использованием О(1) и использованием ровно одной переменной. Мы, например, не можем переложить начало очереди в конец, не испортив какого-нибудь счётчика (если он зачем-то нужен).
        0
        Недавно столкнулся с такой задачей: «Объединить две очереди таким образом, чтобы суммарная очередь была отсортирована».
        Мне кажется или статья о другом

        Как отсортировать очередь используя 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)
        После исполнения данного кода получаем такое же состояние очереди, как и до исполнения.
          0
          Почему-то всё форматирование съехало..
          +1
          Для этой задачи есть уже давно было придумано более изящное, на мой взгляд решение. Стандартная реализация очереди с приоритетом (ваш случай когда весами элементов являются сами элементы) отлично реализуется на структуре heap, где элементы хранятся в сплошном массиве и каждый новый элемент становится в свою позицию простыми обменами не более чем за O(log N). Собственно всем известный heapsort как раз так и реализован. Для слияния нужно просто одну очередь по-поэлементно влить в другую.
            +1
            Действительно, я тоже не понял, зачем заниматься ерундой, когда очередь с приоритетами (как идея) существует не один десяток лет. С другой стороны, в силу некорректности формулировки задания, нельзя точно сказать, с каких данных мы начинаем и что считать дополнительной памятью. На месте исполнителя я требовал бы более чёткой формулировки (что именно дано и в каком виде оно перед нами изначально). Потому что если очереди уже даны в некотором виде (например, в виде списков), то я не вижу каких-то способов использовать heap без нарушения правила одной переменной, тогда придётся извращаться. Если данные даны абстрактно, то можем считать, что они даны в массиве. Дальше всё зависит от того, в одном они массиве или в двух...
            Короче, обычно когда задачу формулируют именно так, я возвращаю её автору со словами "сам решай", потому что так задачи не ставятся, когда от трактовки формулировки зависит метод решения.
            Кроме того, неплохо было бы понимать, для чего вообще даются подобные задачи. Одно дело для разминки, а другое, когда есть реальная необходимость экономить память. В первом случае это может представлять интерес, конечно, а во втором случае память нужно начинать экономить, например, тем, что не писать сообщения типа "queue is full!", не писать на Python и всё-таки хранить данные иначе.
            0
            Опасная конструкция:
            def get_list(self):
            return self.queue
            Отдаете ссылку на приватный атрибут, т.е. можно изменять очередь вне класса
            лучше так сделать:
            return list(self.queue)
              0
              Да, вы правы. Поверхностная копия лучше, чем ссылка на оригинал
              0
              Причём требование для сортировки такое: не использовать никаких промежуточных объектов, кроме одной переменной, каким бы медленным алгоритм ни был.

              Так ведь steps это вторая переменная. Получается, это требование нарушено?
                0
                Получается, что так. Либо можно что-нибудь посчитать, либо запомнить (или переставить) элементы в очереди — но не одновременно.
                С другой стороны, ничто не запрещает нам добавить новый пустой элемент в очередь и использовать его для сортировки пузырьком?
                  0
                  Нет, ну переменные счётчика использовать можно. Главное не использовать дополнительных очередей, списков, массивов — таких вот объектов. То есть только одну промежуточную переменную можно использовать, но не больше.
                  0
                  Без счётчиков, но с дополнительным пустым элементом в очереди:
                  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();
                    0
                    Почему бы не сделать проще:

                    Слить две очереди в одну.
                    Отсортировать с учетом требований.
                      0
                      Дело в том, что слияние очередей не так важно, как их сортировка. Сложность задачи заключалась именно в разработке алгоритма сортировки, который я и привёл.
                        0
                        Один массив (возможно, и очередь) можно рекурсивно отсортировать вообще без дополнительных/временных переменных.
                          0
                          и без выделения log N под стек?
                            0
                            это уже вряд ли)
                      0
                      На питоне можно было проще — на голых списках без создания собственного класса. 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)

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое