Keine Terminierung beim Quicksort |
01.10.2016, 10:20 | Auf diesen Beitrag antworten » | ||||||||||
hollebolle | Keine Terminierung beim Quicksort 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
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. |
||||||||||
|
|||||||||||
01.10.2016, 10:23 | Auf diesen Beitrag antworten » | ||||||||||
eulerscheZahl | 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. |
||||||||||
01.10.2016, 13:44 | Auf diesen Beitrag antworten » | ||||||||||
hollebolle | 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|