Ordenando una pila en orden ascendente?

Question

¿Cuál es el mejor método para ordenando una pila en orden ascendente? I se encontró con esta pregunta de la entrevista y me encontré con algunos problemas para encontrar la mejor y más eficiente solución.

Hay dos métodos que se me ocurren.

1. hacer estallar todos los contenidos de la pila y almacenarlos en una matriz, y luego ordenar la matriz en
   O(nLog n) y luego empujar el contenido copia de la pila. No es la mejor manera ....

2. Haz la aplicación recursiva de la pila para la clasificación que

void sort(stack) 
{ 
    type x; 

    if (!isEmpty(stack)) { 
     x = pop(stack); 
     sort(stack); 
     insert(x, stack); 
    }   
} 

void insert(x, stack) 
{ 
    type y; 

    if (!isEmpty(stack) && top(stack) < x) { 
     y = pop(stack); 
     insert(x, stack); 
     push(y, stack); 
    } 
    else { 
     push(x, stack); 
    } 
} 

Pero el segundo método parece estar haciendo demasiadas llamadas recursivas y la sobrecarga será un problema si la pila pasa a ser realmente grande.

¿Es posible resolver este problema de una manera mucho mejor para la mejor complejidad de espacio y tiempo?

Hay tantas llamadas recursivas, (subproblemas superpuestos), ¿esto es un contendiente para el tipo de problemas dynamic programming?

¿Cuál sería la mejor manera de resolver esto? ?

Answer 1

Es una pila. No puedes ver nada más que el valor superior. Tendrás que abrir todo al menos una vez e insertar todo al menos una vez. El primer método está bien.

Si las operaciones de la pila son costosas pero tiene un límite de tiempo, utilice la ordenación por inserción a medida que está apareciendo y puede presionar tan pronto como finalice su última operación. Pero estás diciendo que esto está en C++, así que dudo que estemos considerando tal escenario.

Answer 2

Lo puede resolver eliminando la recursión. Para esto, simplemente usa un bucle que itera debajo de una pila hasta que esté vacío.

Por ejemplo, la pseudo código:

Linekd Stack stack = new List(); 

while stack is not empty then 

    element <- stack removes peek 

    // Recursiong 
    push new elements on stack 

end 

Answer 3

Este problema no puede tener menos de complejidad O (n^2). Para referencia adicional, refiera here