Quicksort |
18.04.2010, 17:34 | Auf diesen Beitrag antworten » |
Hellboy256 | Quicksort 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? |
|
|
09.06.2010, 22:53 | Auf diesen Beitrag antworten » |
CookieMonsta | 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 |
23.09.2011, 09:16 | Auf diesen Beitrag antworten » |
humanetiggor | Road to truth 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, 10:21 | Auf diesen Beitrag antworten » |
numerouno | RE: Quicksort 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. |
Anzeige | |
|
|
01.10.2011, 11:56 | Auf diesen Beitrag antworten » |
sk1982 | RE: Quicksort 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |