Warteschlange Sortierung

Question

Ich möchte eine Warteschlange von Zeichenfolgen sortieren.

nur Funktionen in meinem arsenel sind:

queue.count() - returns size 
queue.pop() - return head, delete head 
queue.push(String str) - add string at head 
queue.get(int index) - return value stored at index 

queue object - original strings stored in here 
temp object - sorted strings should go here 
temp1 object - temporary queue for help with sorting 

Ich habe die Warteschlange wie folgt initialisiert:

String a[] = {"First", "third", "second"}; 

    for (int i = 0; i < 3; i++) 
    queue.push(a[i]); 

ich versucht habe und diesen Code geschrieben:

temp.push(queue.peek()); 

    for (int i = 0; i < queue.count(); i++) 
    { 
    for (int j = 0; j < temp.count(); j++) 
    { 
     if (temp.get(j) != queue.get(i)) 
     { 
     if (temp.get(j) > queue.get(i)) 
     { 
      temp.push(queue.get(i)); 
     } 
     else 
     { 
      for (int k = 0; k < temp.count(); k++) 
      temp1.push(temp.pop()); 

      temp.push(queue.get(i)); 

      for (int k = 0; k < temp1.count(); k++) 
      temp.push(temp1.pop()); 
     } 
     } 
    } 
    } 

sollte es Rückkehr:

erste

Sekunden

dritte

Aber es gibt:

erste

Sekunden

dritte

dritte

Sekunde

Answer 1

Ich nehme an, dass dies eine Übung im kreativen Denken ist, anstatt ein Problem der realen Welt. Obwohl so etwas in der Vergangenheit ein echtes Problem für Bandlaufwerke und wenig Speicher gewesen sein könnte.

Wenn Sie nur die pop und push Methoden der Warteschlange verwenden können, dann können Sie tun, was im Grunde eine wirklich ineffiziente Blasensortierung ist. Dies erfordert O (n^2) -Operationen und O (1) zusätzlichen Raum.

Pseudocode:

size = queue.Count 

for i = 0 to size-1 
    largest = queue.pop() 
    for j = 1 to size-1 
     temp = queue.pop() 
     if temp > largest 
      queue.push(largest) 
      largest = temp 
     else 
      queue.push(temp) 
     end if 
    end for 
    queue.push(largest) 
end for 

So das erste Mal durch die Schleife, macht es sicher, dass der größte Posten am Ende der Warteschlange ist. Das nächste Mal durch, es wird das zweitgrößte an seiner Stelle, etc.

Es gibt einige kleinere Optimierungen möglich, aber sie haben keinen Einfluss auf die Laufzeit sehr, weil Sie noch jedes Element pop und drücken müssen jedes Mal durch die Schleife.

Es gibt einen möglichen frühen Ausgang, genau wie es für Blasensortierung ist. Wenn in jeder Iteration der inneren Schleife, temp > largest, dann wissen Sie, dass die Warteschlange in Ordnung ist. Das könnte eine sinnvolle Optimierung sein, und es ist nicht schwer zu implementieren:

size = queue.Count 
isInOrder = false 
while isInOrder == false 
    isInOrder = true 
    largest = queue.pop() 
    for j = 1 to size-1 
     temp = queue.pop() 
     if temp > largest 
      queue.push(largest) 
      largest = temp 
     else 
      queue.push(temp) 
      isInOrder = false 
     end if 
    end for 
    queue.push(largest) 
end while 

Vorausgesetzt, dass Sie auch get Methode der Warteschlange der nennen können, gibt es wahrscheinlich einen schnelleren Weg, dies zu tun. Immer noch O (n^2) Komplexität, aber die reale Laufzeit könnte möglicherweise besser sein. Ich müsste darüber nachdenken.