Quicksort 3 Median funktioniert nur unzuverlässig

Reality

Top Contributor
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. ;)
 
Zuletzt bearbeitet:

Reality

Top Contributor
Aber das hat sich doch erledigt. :)
Ich habe bei einer Fallunterscheidung versehentlich beide quicksort-Methode aufgerufen, deswegen hat das solange gedauert. ;)

L. G.
Reality
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Quicksort Rang ausgeben Allgemeine Java-Themen 2
M Quicksort Partition Allgemeine Java-Themen 0
Zrebna Quicksort-Algorithmus - zufälliges Pivot wählen Allgemeine Java-Themen 6
Kirby.exe Quicksort Allgemeine Java-Themen 5
N Quicksort Programm hängt sich auf Allgemeine Java-Themen 6
D Pivot-Wahl beim QuickSort steigert die Effizienz, eine Lüge??? Allgemeine Java-Themen 17
D QuickSort (Pivotelement) Allgemeine Java-Themen 2
S Alphabetische sortierung mit Quicksort Allgemeine Java-Themen 10
S Quicksort Problem Allgemeine Java-Themen 4
S Frage zu dieser Quicksort Variante Allgemeine Java-Themen 2
G QuickSort Allgemeine Java-Themen 7
G ArrayList mit quicksort sortieren Allgemeine Java-Themen 9
D QuickSort, Interface Allgemeine Java-Themen 2
G QuickSort mit 2 Kriterien durchführen Allgemeine Java-Themen 12
T Pivotelement als Median von fünf Elementen Allgemeine Java-Themen 2
dayaftereh Median Suchalgorithmus Allgemeine Java-Themen 4
G Programm zur Berechnung von Summe, Median, Erwartungswert, usw von einem Array Allgemeine Java-Themen 7
V Wie funktioniert das Schlüsselwort "final" von Java? Allgemeine Java-Themen 19
M Apache Proxy Weiterleitung auf Tomcat funktioniert nicht wie gewünscht Allgemeine Java-Themen 1
W While Schleife funktioniert nicht ganz Allgemeine Java-Themen 4
H do-while Schleife funktioniert nicht wie ich es möchte Allgemeine Java-Themen 7
ERlK JDA Code funktioniert nicht? Allgemeine Java-Themen 4
B HeapSort für Array of Strings funktioniert nur teilweise Allgemeine Java-Themen 3
stormyark TikTakToe funktioniert nicht Allgemeine Java-Themen 10
T Remove bei ArrayList funktioniert nicht Allgemeine Java-Themen 2
M Map<String,String>funktioniert nicht richtig Allgemeine Java-Themen 4
P String.replace() funktioniert nicht? Allgemeine Java-Themen 3
boschl2000 Springerproblem-Implementierung funktioniert nicht richtig Allgemeine Java-Themen 1
F Getter Methode aufrufen funktioniert nicht Allgemeine Java-Themen 1
N Regulärer Ausdruck funktioniert nicht Allgemeine Java-Themen 6
Lukas2904 Wie funktioniert ein KeyLogger? Allgemeine Java-Themen 3
Tobero Meine Funktion für das beinhalten eines Punktes in einem Kreis funktioniert nicht Allgemeine Java-Themen 5
1Raini Java if-Abfrage funktioniert nicht! Allgemeine Java-Themen 3
Killunox MaxHeap Zuweisung unter Linux funktioniert nicht Allgemeine Java-Themen 1
I Wieso funktioniert das nich? Allgemeine Java-Themen 5
Dann07 MP3 Datei abspielen funktioniert nicht Allgemeine Java-Themen 6
O Aus JAR-Datei erstellte EXE-Datei funktioniert nicht Allgemeine Java-Themen 10
A Mp3 Player funktioniert nicht Allgemeine Java-Themen 0
X JNA funktioniert nicht mehr Allgemeine Java-Themen 4
bueseb84 FolderWatcher mit WatchService funktioniert nur bedingt Allgemeine Java-Themen 5
Drachenbauer Division mit Int funktioniert nicht Allgemeine Java-Themen 3
O docx-Datei erzeugung mit DocXStamper funktioniert nicht Allgemeine Java-Themen 2
F Schleife funktioniert nicht richtig Allgemeine Java-Themen 13
T Split() Methode funktioniert nicht?! Allgemeine Java-Themen 11
L Tesseract-OCR 4.0 unter Linux funktioniert nicht Allgemeine Java-Themen 3
J Wie konkret funktioniert das Modulsystem unter Java 11? Allgemeine Java-Themen 4
J Neuronales Netz funktioniert mal und mal nicht. Allgemeine Java-Themen 3
T Umlaute in Eclipse einlesen funktioniert nicht Allgemeine Java-Themen 16
A Methodenaufruf funktioniert nicht richtig Allgemeine Java-Themen 5
C WindowBuilder Design funktioniert nicht Allgemeine Java-Themen 0
J FTPSClient funktioniert nicht Allgemeine Java-Themen 4
H IDEA IntelliJ Java Mail funktioniert nach Export nicht mehr! Allgemeine Java-Themen 1
M Operatoren Warum funktioniert diese überprüfung nicht? Allgemeine Java-Themen 7
R jar-Datei funktioniert nicht Allgemeine Java-Themen 2
E Open Declaration Funktioniert nicht Allgemeine Java-Themen 0
R Verschlüsselung funktioniert nicht Allgemeine Java-Themen 5
RalleYTN requires transitive funktioniert nicht? Allgemeine Java-Themen 7
R Bruteforce hashes mit multithreading. Funktioniert das so? Allgemeine Java-Themen 0
P Best Practice Wieso funktioniert der Modulo - Operator nicht? Allgemeine Java-Themen 2
HarleyDavidson Eigener PropertyChangeListener funktioniert einfach nicht Allgemeine Java-Themen 3
J Exclude funktioniert nicht Allgemeine Java-Themen 2
K .jar funktioniert nicht vollständig Allgemeine Java-Themen 1
P Java https proxy (-Dhttps.proxyHost) Start-Parameter funktioniert nicht? Allgemeine Java-Themen 2
L Auswertung eines Testes funktioniert nicht Allgemeine Java-Themen 37
O Fahrenheit/Celsius Converter funktioniert nicht Allgemeine Java-Themen 2
M Serialisierung funktioniert nicht Allgemeine Java-Themen 9
D Collections.sort funktioniert nicht in exportierten .class Dateien Allgemeine Java-Themen 10
J Arrays auf gleichheit untersuchen funktioniert nicht Allgemeine Java-Themen 11
P GUI: ArrayList anzeigen funktioniert nicht Allgemeine Java-Themen 5
H Timer funktioniert nicht? Allgemeine Java-Themen 3
R javax.comm --> Programm funktioniert nach Export nicht mehr Allgemeine Java-Themen 0
O Mein JButton Array funktioniert nicht Allgemeine Java-Themen 3
R Erste Schritte Object reference funktioniert nicht. Wie mach ichs richtig? Allgemeine Java-Themen 3
J If Abfrage funktioniert nicht Allgemeine Java-Themen 4
R Objekt funktioniert nicht auf iOS Allgemeine Java-Themen 15
U PersistenceManager.createEntityManager funktioniert nicht Allgemeine Java-Themen 3
D Java Datei nach Eclipse Export funktioniert nicht Allgemeine Java-Themen 0
M Eigene forEach()-Methode funktioniert nicht. Allgemeine Java-Themen 2
H File.listFiles() funktioniert nicht... Allgemeine Java-Themen 10
JG12111989 Auswertung von Fragebogen funktioniert nicht! Allgemeine Java-Themen 7
M Primzahlberechnung funktioniert nicht. Allgemeine Java-Themen 4
A JFreeChart funktioniert nicht :( Allgemeine Java-Themen 6
C file.delete() funktioniert bei zweiten aufruf nicht mehr Allgemeine Java-Themen 3
F Datei einlesen funktioniert nicht Allgemeine Java-Themen 3
A Debugger im Java-Editor funktioniert nicht Allgemeine Java-Themen 5
B DB-Zugriff einer Webanwendung funktioniert nicht mit Java 7 Allgemeine Java-Themen 2
B Web-Anwendung funktioniert mit Java 1.8, aber nicht mit Java 1.7 (auf Client) Allgemeine Java-Themen 5
J Swing Cursor.WAIT funktioniert nicht nach JFileChooser Allgemeine Java-Themen 1
P Wie funktioniert das Feedback eines Klicks auf eine Java GUI Allgemeine Java-Themen 10
F JTextField funktioniert nicht Allgemeine Java-Themen 6
Athena Programm funktioniert nur beim Debugging korrekt, sonst nicht. Allgemeine Java-Themen 1
S CSV Eintrag der nächsten Zeile auslesen funktioniert nicht Allgemeine Java-Themen 8
S Command funktioniert in Kommandzeile aber nicht mit ProcessBuilder bzw. Runtime.exec auf MAC Allgemeine Java-Themen 3
G Verschlüsselungsalgorythmus funktioniert nicht Allgemeine Java-Themen 2
buggy84 Ausführen einer Batch mit Parameterübergabe funktioniert nicht richtig Allgemeine Java-Themen 18
G Befehl funktioniert in Eclipse allerdings nicht in einer Jar-Datei Allgemeine Java-Themen 3
N Werte aus Arrays auslesen funktioniert nicht Allgemeine Java-Themen 5
W getResources funktioniert nur in Eclipse, nicht in JAR Allgemeine Java-Themen 2
S Methode funktioniert nicht als ActionListener Allgemeine Java-Themen 4
M exec() funktioniert nicht Allgemeine Java-Themen 1

Ähnliche Java Themen

Neue Themen


Oben