Hi, ich verstehe nicht genau, wie sortiert werden soll. Kann mal jemand ein Beispiel mit Zahlen posten?
Ja, das steht in jedem Buch besser beschrieben. Die Aufgabe sieht aber einen abweichenden Algorithmus vor, deshalb auch "verbessert"! "…und bin so klug als wie zuvor"
klug wird nur der der klug fragt ;)
die 'Verbesserungen' sind Hinweise für eine schnellere Implementation des Algorithmus
(keine Auswirkung auf Sortiervorgang)
und doch eigentlich verständlich?
noch mal neu formuliert:
- nach 5 Durchgängen brauchst du in den folgenden Durchgängen
die letzten 5 im Array nicht mehr prüfen,
da diese schon garantiert richtig sind,
- wenn sich in einem Durchgang nichts mehr ändert,
bist du fertig mit sortieren
Hab da mal ne Frage….wieviele Vergleiche und Tausche habt ihr bei QuickSort wenn ihr den MatrikelComparator verwendet?
Ich komm auf ca. 3100 Tausche und ca. 3500 Vergleiche…kann das stimmen? An welcher Stelle erhöht ihr den die Comparisons?
Ist dieses Verfahren nicht abhängig vom Pivot-Element? Wie habt ihr das denn gewählt? bzw. was ist eine geschickte Wahl?
Ich hab einfach das mittlere Object ausgewählt…
Jo… da habe ich auch gerade ein problem: wir koennen doch nur per Comparator.compare auf die objekte zugreifen, und so keinen mittelwert fuer quicksort berechnen, weil wir an die _werte_ nicht drankommen, oder?
Ich habe:
Anzahl der checks: 719100…
Anzahl der Tauschungen insgesammt: 358508
was geht?
- VideoSven
und so keinen mittelwert fuer quicksort berechnen, weil wir an die _werte_ nicht drankommen, oder?
Ja. Ist aber fuer Quicksort gar nicht noetig, irgendein Element ist voellig ausreichend.
@ VideoSven
Naja also im Saake und Sattler Buch steht, dass für QuickSort gilt n*log n an maximalen Vergleichen…das wären ca. 3600 …
deine Zahlen hören sich eher nach BubbleSort an…kann das sein?
Oooops… ich seh gerade dass du _nicht_ bubblesort meintst - sorry! Meine werte sind natuerlich fuer bubblesort - liegen die zahlen fuer bubblesort im gruenen bereich?
- VideoSven
Ja für BubbleSort hab ich auch solche Werte bekommen…wahnsinnig hoch nicht war? Und das erst bei 1200 Studenten…wenn man sich überlegt, wieviele Studenten es in HH gibt…wenn die alle nach diesem Prinzip sortiert wären…bräuchte man wohl schon ne Weile bis sie richtig geordnet wären…
http://www11.informatik.tu-muenchen.de/lehre/lectures/ws1999-00/einfinfo/einfinfo-course6.3.html
ACHTUNG! Das auf den Folien angegebene QuickSort ist in Wirklichkeit MergeSort! Also nicht für die Aufgabe verwenden.
hoppla ;)
war nicht beabsichtigt ;)
