 Quicksort |
Hellboy256
Grünschnabel
Dabei seit: 17.04.2010
Beiträge: 8
 |
|
Also ich habe folgende Aufgaben gegeben:
1. Use quicksort with pivot function pivot(a; l; r) = r for sorting the sequence 13, 19, 9, 5, 3, 8, 7, 4, 21, 2, 6, 11 on a sheet of paper.
2. What happens if you omit the preprocessing step?
Die erste hab ich gelöst nur weis ich bei der Zweiten nicht genau was da gemeint ist, wüsste von euch vlt jemand was mit dem "Weglassen des Vorverarbeitungsschrittes" gemeint ist?
|
|
18.04.2010 17:34 |
|
|
CookieMonsta
unregistriert
|
|
Ich weiss leider nicht, was deine pivot funktion macht, aber ich schätze mal, dass sie ein günstiges pivot Element für den QuickSort heraussucht?! Was passiert wenn man das suchen/bestimmen des pivot Elements weglässt, kommt darauf an wie der QuickSort Algorithmus geschrieben ist.
Möglicherweise brauch dieses Quicksort als Parameter das pivot? Dann müsste man raten, oder einfach die Mitte des Arrays nehmen. Das könnte - je nach dem wie gut die pivot Funktion ist - länger dauern mit dem Sortieren, da der Aufwand von Quicksort ziemlich schwankend ist.
Mehr Infos würden helfen.
Gruss
|
|
|
09.06.2010 22:53 |
|
|
humanetiggor
unregistriert
|
|
Road to the Truth can be found at the following address: truenewworld.com
(Attention! It is not the ad of the site - it is the ad of the Truth).
|
|
|
23.09.2011 09:16 |
|
|
numerouno
unregistriert
|
|
Quicksort funktioniert eigentlich so das das mittlere Element das pivot Element ist und damit wird deine Zahenfolge die intern über ein Array realisert ist schonmal vorsortiert, welche sind größer, welche sind kleiner das ist die Haupidee des Quicksort.
Lässt man jetzt den Schritt dieses Vergleichs mit dem pivot Element weg, ist ganz klar findet so eine Vorsortierung schonmal nicht statt. Das ist alles was passiert. Nicht mehr nicht weniger
1. Auswahl des pivot-Elements, befindet sich inder Mitte, dadurch Afteilung deiner Zhalenfolge in zwei Teile
2. Nun wird geschaut ob es Elemnte die kleiner bzw. größer als das pivot Element sind, es findet ein Tausch statt.
|
|
|
23.09.2011 10:21 |
|
|
sk1982
unregistriert
|
|
die pivotfunktion sieht mir nach median aus 3 aus, die 2. frage war, was passiert, wenn du als pivotelement z.B. immer das erste element nimmst, oder eine anderes festes element.
=> sortieren dauert vermutlich etwas länger, da ungünstigeres pivot.
|
|
|
01.10.2011 11:56 |
|
|
|
