Ordenando una cola usando la misma cola

Question

Me han hecho esta pregunta y creo que es posible, sin embargo, me está costando crear un algoritmo para hacerlo. Las restricciones son que no puede usar ninguna otra estructura de datos ni crear otra cola. También solo puedes usar en cola, dequeue y peek (NO una cola de prioridad).

Gracias por contribuir :)

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) 

ascendente en orden, se ejecuta en O (^ 2 n) el tiempo, en el espacio O (1) (es decir, la cola es O (espacio n), y el espacio extra que se requiere por el algoritmo es O (1))

Explicación:

Esencialmente, iterar a través de la cola de n veces, cada vez los costes de iteración 2n.

En cada iteración, pasamos por toda la cola y seleccionamos el mínimo dentro del número de elementos pertinente. Entonces, al principio, el número de elementos relevante es n, ya que queremos el mínimo de todos. La próxima iteración queremos el mínimo de los primeros n-1 elementos, y luego n-2 elementos, etc. Dado que el algoritmo se apilan estos mínimos al final.

Una vez que encontramos el mínimo, necesitamos iterar sobre toda la pila nuevamente para poder arrebatarlo y apilarlo al final.

La idea principal aquí, es que un dequeue seguido de un enqueue de ese mismo elemento nos permitirá iterar sobre la cola y verificar el mínimo/máximo conservando el orden.

Answer 2

BubbleSort utilizando una cola:

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