Also, ich hab mich bei meiner Lösung so ziemlich an dem Algorithmus, den man in dem Buch "Algorithmen & Datenstrukturen" v. Saake u. Sattler findet orientiert. Das Sortieren klappt auch allerdings ist die Anzahl der Vergleiche viel zu hoch! ca 15377!!!
Woran kann das liegen? Ich erhöhe die Anzahl der comparisons in einer methode compare(o1,o2), die den Vergleich einfach an den Comparator weiterreicht.
Ich blick da einfach nich mehr durch!
Also um die 16000 Vergleiche bei 1000 Listenelementen finde ich eigentlich ziemlich realistisch.
Ich meine mich zu errinnern etwas ähnliches gehabt zu haben.
Bedenke das du wesentlich mehr Vergleiche als Vertauschungen benötigst.
Gruß Dosenwein
wieso sollten es denn zu viele Vergleiche sein?
wenn du genau weisst wieviele zu erwarten sind,
dann kannst du das vielleicht auch für 10 Leute ausrechnen?
und schauen was das Programm stattdessen macht?
hab mal ne lustige seite gefunden wo QuickSort sehr schoen erklaert wird, vielleicht hilft es ja noch jemadem ausser mir, das richtig zu verstehehen ;-)
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html
ich habe bei Quicksort ca. 10000 Vergleiche und 3000 Vertauschungen
Ich dachte die Anzahl der der Vergleiche sollte im Durchschnitt bei n*log(n) liegen. Bei 1200 Studenten wäre das ~3600.
log(1200) = 10.22 [es ist log_zurbasis2_von_n]
also:
1200 * 10.22 = 12274
ich habe bei Quicksort ca. 10000 Vergleiche und 3000 Vertauschungen
Wie hast du das geschafft?!
Ich bin bei meiner Implentierung nach der Folie mit dem Struktogramm vorgegangen und habe nun etwa 16800 Vergleiche und 2800 Vertauschungen
Ist doch beides im Bereich des moeglichen. Wir liegen mit den Vergleichen sogar noch ein wenig hoeher. Aber ich wuerd sagen, Hauptsache es funktioniert, oder? Immerhin stand bei Quicksort nicht dabei, dass wirs noch sonderlich optimieren sollen.
Also wir kommen bei Quicksort auf ~3200 Wechsel bei ~9100 Vergleichen.
Bei BetterBubbleSort liegen wir bei ~700.000 Wechseln bei fast gleich viel Vergleichen.
