1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

Sortierverfahren

Dieses Thema im Forum "Sonstige Sprachen" wurde erstellt von Heinzi1991, 4. November 2014.

  1. Heinzi1991

    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
     
  2. sheel

    sheel I love Asm Administrator

    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 (Text):
    1. solange A nicht leer
    2. {
    3.         PopPush(A,C)
    4.         solange A nicht leer
    5.         {
    6.             wenn A<C
    7.             {
    8.                 PopPush(C,B)
    9.                 PopPush(A,C)
    10.             }
    11.             sonst
    12.             {
    13.                 PopPush(A,B)
    14.             }
    15.         }
    16.         solange B nicht leer
    17.         {
    18.             PopPush(B,A)
    19.         }
    20. }
    21. solange C nicht leer
    22. {
    23.     PopPush(C,A)
    24. }
    Laufzeit grob n*n/2 + n = O(n^2)
     
    Zuletzt bearbeitet: 5. November 2014
  3. Heinzi1991

    Heinzi1991 Erfahrenes Mitglied

    vielen vielen dank und wenn c < a ist meine compare funktion nehme ich einmal an, weil die gibt true or false aus!
     
  4. sheel

    sheel I love Asm Administrator

    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.
     
  5. Heinzi1991

    Heinzi1991 Erfahrenes Mitglied

    nein also compare gibt als ergebnis true or false aus! also s1 > s2 true sonst false
     
  6. sheel

    sheel I love Asm Administrator

    Dann passt ja alles: "wenn C<A" ist also "wenn Compare(A,C)"
     
  7. Heinzi1991

    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
     
  8. sheel

    sheel I love Asm Administrator

    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?