das pivotelement ist nicht immer die letzte Stelle oder?

  • Ja ich weiss die Frage ist blöd, aber ich hab bis jetzt noch nie eine Folge gesehen, bei der das Pivotelement z.B. genau in der Mitte vorkommt.
    Wie soll ich die Folge sortieren, wenn genau dieser Fall auftritt?


    z.B. 9 0 5 8 2 6 3 1 4 2, da kann ich die letzte Stelle nicht als Pivot wählen.



    Zitat

    Original geschrieben von eXe
    das pivotelement ist doch frei wählbar hängt von der implementierung ab ob mittleres letztes oder sonst eines


    wieso sollte 2 da nicht als pivotelement gehen?


    edit: z.B. dann halt diese Folge 9 0 5 8 2 6 3 2 4 1


    oder noch fieser: 9 8 7 6 5 4 3 2 1

    Religion ist ein Glaube,
    Wissenschaft als Teilgebiet ist ein Glaube,
    die Wahrheit liegt in der Gegenwart des Menschen.

  • Heeelp bin am Verzweifeln!!! :(


    9 0 5 8 2 6 3 2 4 1 p=4
    2 0 5 8 2 6 3 9 4 1
    2 0 3 8 2 6 5 9 4 1
    2 0 3 2 8 6 5 9 4 1
    2 0 3 2 4 6 5 9 8 1
    -----------------------------------


    2 0 3 2 p=2
    2 0 3 2
    --------------------------------------
    ________6 5 9 p=9??


    Und wie geht's weiter? :confused:

    Religion ist ein Glaube,
    Wissenschaft als Teilgebiet ist ein Glaube,
    die Wahrheit liegt in der Gegenwart des Menschen.

  • muss da ganz links nicht ein "stop"element (kleinstes Element) stehen? habe nämlich genau das gleiche problem bei <7, 1012, 13, 128, 5, 4711, 34> ...

  • jeuneS2 : ist viel mehr Aufwand, bei jedem Durchlauf auf die Grenzen zu überprüfen, als einfach das Stoppelement einzubauen.


    Jeff_Mills : Die Wahl des Stoppelements kommt auf die Implementation des Quicksorts an. Wenn man eine Quicksortimplementierung mit:
    Zeile 5: >=
    Zeile 8: <
    Zeile 9: <
    Zeile 12: >= (oder >, ist egal)
    verwendet, muß daß Stoppelement natürlich < dem Minimum sein und nicht nur <=.
    Nur wenn man eine Implementation mit:
    Zeile 5: >=
    Zeile 8: <=
    Zeile 9: <
    Zeile 12: >=
    verwendet, reicht es, wenn das Stoppelement <= dem Minimum ist.

    I'm a pessimist because of intelligence, but an optimist because of will. -- Antonio Gramsci