Frage zum Quicksortverfahren

  • Allgemein

  • Vorudor
  • 1072 Aufrufe 3 Antworten

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Frage zum Quicksortverfahren

    Hallo!

    Wäre dankbar, wenn mir jemand beim Quicksort behilflich sein könnte.

    Wenn ich das wort "PROSITNEUJAHR" mi QS ordnen möchte und mit dem letzten R als Pivot beginne, dann ergibt sich im fünften Schritt, dass das Pivot-"R" an die Stelle des "U" tritt.

    Welches ist nun das neue Pivot für die rechte Seite?

    Kann mir vielleicht jemand die einzelnen Sortierschritte aufschreibn bzw erklären?


    LG

  • Wiki sollte eigentlich alle Fragen klären können :read:

    Wie sortierst du denn genau? Hier mal als Beispiel, wie es sein müsste, wenn du jeweils das letzte Element als Pivot wählst, gleiche Elemente links einordnest und die Teillisten von links nach rechts durchgehst.

    Pivot jeweils fett:

    prositneujahr

    proinejahr r stu

    proinejah r r st u

    ae h proinj r s t u

    a e h ij j pron r s t u

    a e h i j j n pro r s t u

    a e h i j j n o pr r s t u

    a e h i j j n o p r r s t u

    aehijjnoprrstu

    Hoffe, man kann das so nachvollziehen.

  • Naja, Wiki hilft nicht, wenn es um einen Quicksort geht, der auch doppelte Elemente berücksichtigen muss.

    Also meine Vorgangsweise:

    Um es mir leichter zu machen hab ich den Buchstaben Zahlen zugeordnet (Stelle im Alphabet) - dann sieht PROSITNEUJAHR so aus:

    16|18|15|19|9|20|14|5|21|10|1|8|18

    Pivot ist rot:
    1. Schritt: 16|8|15|19|9|20|14|5|21|10|1|18|18|
    2. Schritt: 16|8|15|1|9|20|14|5|21|10|19|18|18|
    3. Schritt: 16|8|15|1|9|10|14|5|21|20|19|18|18|
    4. Schritt: 16|8|15|1|9|10|14|5|18|20|19|18|21|


    So, bis hier kenn ich mich aus.
    Jetzt allerdings, wo ich meinen 18 auf grün gebracht habe und damit sortiert habe ich zwei Seiten, welche ich seperat sortieren muss.
    Mir is nicht klar, welches Element ich auf der rechten Seite als Pivot nehmen muss. denn würde ich 21 nehmen, dann gibts kein größeres Element mehr und ich kann nicht mehr sortieren. Wenn ich 20 nehme komm ich in eine "Endlosschleife" - denn dann tausche ich ständig 18 & 21 hin und her...

    Vielleicht kannst du es mir anhand der Zahlen erklären...

  • Das ist eine Randbetrachtung :-).
    Du hast das Tupel (20|19|18|21).
    Im ersten Schritt kommst Du von links und suchst etwas das größer ist als 21.
    Du findest aber nichts, also läuft Deine Laufvariable bis zur Position der 21.
    Nun kommst Du von rechts und suchts etwas das kleiner ist.
    Gleich die 18 ist ein Treffer. Also zeigt Deine zweite LV auf 18.
    Du erkennst nun, dass rechts an links vorbei gelaufen ist und ersetzt die 21 mit der 21.
    Dann teilst Du die Liste bei der 21. Es bleibt ein Resttupel auf der linken Seite (20|19|18).

    Das Pivotelement ist die 18 ... usw.
    Es ist besser zu schweigen und für einen Narren gehalten zu werden, als zu reden und damit alle Zweifel zu beseitigen ...