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

[4eyes]

Похоже, что вы изобрели Selection Sort.

[4eyes]

Допишу вдогонку.
Попробуйте еще глянуть такие вещи, как:

• Insertion Sort с O(1) на уже отсортированных данных
• Heap Sort c гарантированным O(n log n).

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

[qw1]

И если уж совсем заморочиться, то есть in-place bottom-up quicksort, которая обычно еще быстрее

qsort разве не потребует log(N) памяти под стек вызовов или для хранения маркеров разбиений массива?

[4eyes]

Я ошибся, спасибо. Действительно, придется хранить разбиения, по памяти выйдет log N. И к тому же, я спутал его с bottom-up mergesort с еще большей сложностью по памяти.
Наверное, heap sort идеальный выбор.

[time2rfc]

1) сортируете одну очередь руками с использование свободной переменной
2) сортируете вторую очередь руками с использование свободной переменной
3) делаете слияние двух очередей

[dyadyaSerezha]

Именно. Хоть руками, хоть ногами, хоть с использованием любой библиотечной функции. Алгоритмов вагон и тележка, и почти все не требуют доп.мамяти (то есть, О(1)). В чем проблема-то?

[Mrrl]

Есть разница между использованием О(1) и использованием ровно одной переменной. Мы, например, не можем переложить начало очереди в конец, не испортив какого-нибудь счётчика (если он зачем-то нужен).

[ndkoval]

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

Как отсортировать очередь используя 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)
После исполнения данного кода получаем такое же состояние очереди, как и до исполнения.

[ndkoval]

Почему-то всё форматирование съехало..

[Videoman]

Для этой задачи есть уже давно было придумано более изящное, на мой взгляд решение. Стандартная реализация очереди с приоритетом (ваш случай когда весами элементов являются сами элементы) отлично реализуется на структуре heap, где элементы хранятся в сплошном массиве и каждый новый элемент становится в свою позицию простыми обменами не более чем за O(log N). Собственно всем известный heapsort как раз так и реализован. Для слияния нужно просто одну очередь по-поэлементно влить в другую.

[Zealint]

Действительно, я тоже не понял, зачем заниматься ерундой, когда очередь с приоритетами (как идея) существует не один десяток лет. С другой стороны, в силу некорректности формулировки задания, нельзя точно сказать, с каких данных мы начинаем и что считать дополнительной памятью. На месте исполнителя я требовал бы более чёткой формулировки (что именно дано и в каком виде оно перед нами изначально). Потому что если очереди уже даны в некотором виде (например, в виде списков), то я не вижу каких-то способов использовать heap без нарушения правила одной переменной, тогда придётся извращаться. Если данные даны абстрактно, то можем считать, что они даны в массиве. Дальше всё зависит от того, в одном они массиве или в двух...
Короче, обычно когда задачу формулируют именно так, я возвращаю её автору со словами "сам решай", потому что так задачи не ставятся, когда от трактовки формулировки зависит метод решения.
Кроме того, неплохо было бы понимать, для чего вообще даются подобные задачи. Одно дело для разминки, а другое, когда есть реальная необходимость экономить память. В первом случае это может представлять интерес, конечно, а во втором случае память нужно начинать экономить, например, тем, что не писать сообщения типа "queue is full!", не писать на Python и всё-таки хранить данные иначе.

[codeAXE]

Опасная конструкция:
def get_list(self):
return self.queue
Отдаете ссылку на приватный атрибут, т.е. можно изменять очередь вне класса
лучше так сделать:
return list(self.queue)

[SerjihSklovski]

Да, вы правы. Поверхностная копия лучше, чем ссылка на оригинал

[michael_v89]

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

Так ведь steps это вторая переменная. Получается, это требование нарушено?

[Mrrl]

Получается, что так. Либо можно что-нибудь посчитать, либо запомнить (или переставить) элементы в очереди — но не одновременно.
С другой стороны, ничто не запрещает нам добавить новый пустой элемент в очередь и использовать его для сортировки пузырьком?

[SerjihSklovski]

Нет, ну переменные счётчика использовать можно. Главное не использовать дополнительных очередей, списков, массивов — таких вот объектов. То есть только одну промежуточную переменную можно использовать, но не больше.

[Mrrl]

Без счётчиков, но с дополнительным пустым элементом в очереди:

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]

Почему бы не сделать проще:

Слить две очереди в одну.
Отсортировать с учетом требований.

[SerjihSklovski]

Дело в том, что слияние очередей не так важно, как их сортировка. Сложность задачи заключалась именно в разработке алгоритма сортировки, который я и привёл.

[nikotin77]

Один массив (возможно, и очередь) можно рекурсивно отсортировать вообще без дополнительных/временных переменных.

[4eyes]

и без выделения log N под стек?

[nikotin77]

это уже вряд ли)

[nickolaym]

На питоне можно было проще — на голых списках без создания собственного класса. 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)