Sortierverfahren

Heinzi1991

Erfahrenes Mitglied
Hallo liebe Community

ich habe ein kleines Problemchen:

ich muss einen Algorithmus erstellen für ein Sortierverfahren von Stacks. Ich darf nur zwei Funktionen verwenden:
- PopPush(s1,s2)
- Compare(s1,s2)

weitere infos: der algorithmus muss eine Laufzeit von 0(n^2) haben und es dürfen zusätzlich zum Input-Stack noch zwei weitere Stacks verwendet werden.

Nun mein Problem, ich weiß nicht wie ich die Sache angehen soll.

Vielen Dank im voraus für eure Hilfe
 

sheel

I love Asm
Ich nehme an, man kann auch prüfen, ob ein Stack leer ist (sonst gehts nicht).
Stack A hat die Daten, B und C müssen am Anfang leer sein.
Das fertige Ergebnis ist wieder auf A.

Pseudocode:
Code:
solange A nicht leer
{
		PopPush(A,C)
		solange A nicht leer
		{
			wenn A<C
			{
				PopPush(C,B)
				PopPush(A,C)
			}
			sonst
			{
				PopPush(A,B)
			}
		}
		solange B nicht leer
		{
			PopPush(B,A)
		}
}
solange C nicht leer
{
	PopPush(C,A)
}

Laufzeit grob n*n/2 + n = O(n^2)
 
Zuletzt bearbeitet:

sheel

I love Asm
Ach so...ich dachte eher an etwas, womit man größer/kleiner/gleich ermitteln kann.
zB. 1 für a>b, -1 für a<b, und 0 für a=b
Nur mit "gleich" oder "nicht gleich" kann man auch nichts nach Werten sortieren.
 

Heinzi1991

Erfahrenes Mitglied
also ich bin jetzt deinen pseudocode durchgegangen und hab mir ist aufgefallen, dass bei einer bestimmten stack-ordnung der algo nicht richtig funktioniert! also bei einer zahlenfolge von 1 5 7 3, ist im stack C dann diese reihenfolge 1 3 7 5, hab alles schon probiert, aber ich finde irgendwie keine lösung für deinen code
 

sheel

I love Asm
Vorneweg ein anderes "Problem": Ich hatte vor, dass das kleinste Element am Schluss ganz oben ist.
Im alten Pseudocode ist das Größte oben. Hab das "C<A" oben durch "A<C" ausgetauscht, um das zu ändern.
(Hatte vergessen, dass beim Umschichten von C zu A am Schluss die Reihenfolge ja wechselt)

Das sollte aber nicht verhindern, dass sortiert wird;
und vor allem sollte C am Schluss leer sein.
Kannst du deinen tatsächlichen Code zeigen?