Beispiel 8, Best Case Zahlenfolge

  • In Der Lösung fehlt anscheinend die Best-Case Folge.


    Mir scheint die frage hinfällig, weil Die Anzahl der Vergleiche , das heißt j+i in jedem rekursiven durchlauf immer die gleiche Summe =r-l-1 ergibt.


    Nun wird aber auch immer vertauscht, und zwar wird, falls die Teilfolge bereits vorsortiert ist das Pivotelement gegen sich selbst.


    Ich verstehe auch nicht warum die Bereits vorsortierte Folge der Worst-Case ist. Die Anzahl an Vergleichen ist immer gleich, auch wenn die Vergleiche im Best-Case, paralell ausgeführt werden können. Die Prozessorzeit bleibt gleich!



    Vielleicht kann mich wer Aufklären.

  • Eine Zahlenfolge die von Quick-Sort im Best-Case sortiert wird, waere etwa: 1, 3, 2, 6, 5, 7, 4.


    Das Pivotelement halbiert jedes mal die Zahlenfolge. Dadurch tritt am oeftesten der Fall ein, dass neben den Pivotelement nur noch einelementige Felder sind (die ja dann von Quick-Sort uebersprungen werden). Worst- und Best-Case unterscheiden sich also dadurch, wie oft, QS aufgerufen wird, nicht wieviele Vergleiche innerhalb eines Aufrufs vorkommen.


    Eine bereits sortierte Folge ist deswegen der Worst-Case, weil ja imm er das Element ganz rechts aussen als Pivotelement genommen wird. Es wird mit allen anderen Elementen links davon verglichen. Dadurch dass es aber bereits an seinem endgueltigem Platz steht, wird das Feld nicht irgendwo geteilt, sondern QS wird mit dem gesamten Array (bis auf das letzte Element) noch einmal aufgerufen (der Aufruf fuer die Elemente rechts vom Pivotelement entfallen, weil da ja keine Elemente mehr sind). Auf jeden Fall wird das Vorletzte Element das neue Pivotelement, und wieder mit allen anderen verglichen, usw. Im Endeffekt, wird also jedes Element mit jedem anderem verglichen -> das sind (n^2 - n)/2 Vergleiche -> \Theta(n^2).


    Btw. Ich freue mich ueber alle Hinweise und Korrekturen, aber bitte postet sie in den gleichen Thread wie die jeweilige Loesung.

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!