Hi,
die Laufzeit von Quicksort ist bei sortierten Feldern genauso wie bei BubbleSort quadratisch.
Um dieses Problem zu umgehen, bringt man einfach das (sortierte) Feld im Voraus etwas durcheinander und schon ist die Laufzeit wieder n * log(n).
Meine Umsetzung ist allerdings etwas unzuverlässig.
Ich habe einmal die klassische Quicksort-Methode implementiert und einmal die 3 Median-Methode. Bei der 3-Median-Methode möchte ich die Methode partition nicht komplett neu erstellen. Daher vertausche ich zuerst das mittlere Element mit dem rechten und erst dann rufe ich partition. Das Doofe ist: Anfangs werden tatsächlich die Elemente vertauscht, so wie es sollte, nach einiger Zeit wird allerdings gar nichts mehr vertauscht und die Laufzeit wird wieder quadratisch.
Das Seltsame ist: Packe ich alles nötige in die Methode threeMedianPartition und nehme somit bewusst Redundanz in Kauf, dann ist die Laufzeit, so wie erwartet n * log(n).
Wo liegt also der Fehler?!
Bin für jeden Hinweis dankbar!
Liebe Grüße
Reality
PS: Die Sort-Methoden sind in der Klasse Sort.
die Laufzeit von Quicksort ist bei sortierten Feldern genauso wie bei BubbleSort quadratisch.
Um dieses Problem zu umgehen, bringt man einfach das (sortierte) Feld im Voraus etwas durcheinander und schon ist die Laufzeit wieder n * log(n).
Meine Umsetzung ist allerdings etwas unzuverlässig.
Ich habe einmal die klassische Quicksort-Methode implementiert und einmal die 3 Median-Methode. Bei der 3-Median-Methode möchte ich die Methode partition nicht komplett neu erstellen. Daher vertausche ich zuerst das mittlere Element mit dem rechten und erst dann rufe ich partition. Das Doofe ist: Anfangs werden tatsächlich die Elemente vertauscht, so wie es sollte, nach einiger Zeit wird allerdings gar nichts mehr vertauscht und die Laufzeit wird wieder quadratisch.
Das Seltsame ist: Packe ich alles nötige in die Methode threeMedianPartition und nehme somit bewusst Redundanz in Kauf, dann ist die Laufzeit, so wie erwartet n * log(n).
Wo liegt also der Fehler?!
Bin für jeden Hinweis dankbar!
Liebe Grüße
Reality
PS: Die Sort-Methoden sind in der Klasse Sort.
Zuletzt bearbeitet:
