Hallo zusammen, in meinem Algorithmenskript wird beim Quicksort angegeben, dass bei einer ungünstigen Wahl des Pivots es zu einer Endlosschleife kommen kann. Dabei wird folgendermaßen argumentiert:
Falls
code:
1:
Pivot := arr[end]
gewählt wird und gleichzeitig gilt
code:
1:
arr[end] == max(arr[anf...end])
, also wenn das Pivot das letzte Element ist und gleichzeitig den größten Wert besitzt, dann werden keine Elemente vertauscht und der Teilungspunkt sei end, d.h. das reche Teilfeld ist leer. Das bedeutet: keine Termination.
Das kann ich nicht nachvollziehen. Meiner Meinung nach ist das falsch, denn in dem beschriebenen Falle würde doch jetzt das letzte Element einfach als sortiert markiert und die linke Teilfolge mit n-1 Elementen einfach weiter verarbeitet, oder nicht?
Ich habe auch nichts Ähnliches im Netz gefunden, daher glaube ich, dass diese Aussage oben nicht stimmt.
Wenn du bei der Implementierung nichts falsch machst, terminiert Quicksort auch.
Es kann passieren, dass du quadratische Laufzeit kriegst, z.B. wenn du bei einer bereits sortierten Liste immer das letzte Element als Pivot wählst.
Ja genau, es kann bei einer sortierten oder teilsortierten Folge zu ungünstigen Teilungen und somit zu quadratischer Laufzeit kommen, aber die Angabe keine Termination ist so definitiv nicht korrekt. Ich sehe mich da also durch deine Aussage bestätigt.
