Sortierung von unsortierten Zahlenfolgen
Wir wollen eine unsortierte Folge von Zahlen mittels zweier Stacks
sortieren.
Pseudo-Programmcode:
F = <10, 8, 6, 4, 2, 1, 3, 5, 7, 9>
S1 = emptystack() {Erzeugt den leeren Stack}
S2 = emptystack()
While isemptyfolge(F) = False do
Push(s1,first(F)) {Schiebt den ersten
Buchstaben der Folge F auf Stack S1 }
F = rest(F){Verkleinert F um den ersten
Buchstaben }
While isemptyfolge(F) = False do
If first(F) > top(s1)
do { 1. Buchstabe von F > als oberster Buchstabe von S1 }
Push(s2,top(s1)) { oberster Buchstabe von S1 wird auf S2 geschoben
}
Pop(s1){1.
Buchstabe von s1 wird geleert}
Push(s1,first(F)) { 1. Buchstabe von F wird auf S1 geschoben }
Else {1. Buchstabe von
F <= als oberster Buchstabe von S2}
Push(s2,first(F)){1. Buchstabe von F wird auf S2 geschoben}
End
F = rest(F) {Verkleinert F um den
ersten Buchstaben }
End
While isemptystack(s2) = False do
L = pop(s2) {Holt den Ersten
Buchstaben von S2 in L }
F = concat(F,makefolge(L))
{Erzeugt neue Folge F }
End
End
While isemptystack(s1) = False do
L = pop(s1) {Holt den Ersten Buchstaben von S1 in L
}
F = concat(F,makefolge(L)) {Erzeugt neue Folge F
}
End
Ausgabe: F = <1, 2 3, 4, 5, 6, 7, 8, 9, 10>
(Keine Garantie auf Richtigkeit!)
|
