Сортировка очереди по той же очереди

Question

Мне задали этот вопрос, и я думаю, что это выполнимо, однако мне трудно найти алгоритм для этого.Ограничения в том, что вы не можете использовать какую-либо другую структуру данных или создавать другую очередь.Также вы можете использовать только enqueue, dequeue и peek (НЕ приоритетная очередь).

Спасибо за участие:)

Answer 1

Sort(Q,n):

  for i = 0 to n-1
    min = findMin(Q, n-i, n)
    reorder(Q, min, n)
  end for

findMin(Q, k, n):

  min = infinity

  for i = 1 to n
    curr = dequeue(Q)
    if curr < min && i<=k
      min = curr
    end if
    enqueue(Q,curr)
  end for

  return min

reorder(Q, min, n):

  for i = 1 to n
    curr = dequeue(Q)
    if (curr != min) // I'm assuming that there is a way to differentiate between any two items, this isn't hard to enforce
      enqueue(Q, curr)
    end if
  end for

  enqueue(Q,min)

Сортировка по возрастанию, выполняется за время O (n ^ 2), в пространстве O (1) (т. Е. Очередь занимает пространство O (n), а дополнительное пространство, требуемое алгоритмом, составляет O (1))

Объяснение:

По существу, мы повторяем очередь n раз, каждый раз, когда итерация стоит 2n.

На каждой итерации мы проходимвсю очередь и выбирайте минимум в пределах соответствующего количества предметов.Поэтому сначала соответствующее количество элементов равно n, так как мы хотим получить минимум из них всех.На следующей итерации нам нужен минимум первых n-1 элементов, а затем n-2 элементов и т. Д. Поскольку алгоритм будет суммировать эти минимумы в конце.

Как только мы нашли минимум, нам нужноитерируем по всему стеку снова, чтобы захватить его и сложить в конце.

Основная идея здесь заключается в том, что удаление из очереди, сопровождаемое постановкой в ​​очередь этого же элемента, позволит нам выполнить итерацию по очереди ипроверять минимум / максимум при сохранении заказа.

Answer 2

BubbleSort с использованием очереди:

n <- size of queue
repeat n times
  x <- dequeue item
  repeat (n-1) times
    y <- dequeue item
    if x < y then
      enqueue y
    else
      enqueue x
      x <- y
  enqueue x