Quicksort B - erlaubt zu tauschen?

Benutzeravatar
^Lara^
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 17. Jan 2005 12:57

Quicksort B - erlaubt zu tauschen?

Beitrag von ^Lara^ »

Hey ich bin gerade dabei Quicksort B zu schreiben...
ist es erlaubt, dass man wenn man das mittlere Element gefunden hat es einfach mit dem element am ende tauschen und dann wie in Quicksort A vorzugehen?
Oder soll das Pivotelement erstmal da bleiben wo es ist.. (bis dann gegebenfalls getauscht wird)?

ich hoffe meine frage ist nicht zu wirr..

HaTe
Erstie
Erstie
Beiträge: 11
Registriert: 13. Apr 2008 12:25

Re: Quicksort B - erlaubt zu tauschen?

Beitrag von HaTe »

Ich denke dass das geht (ich habs nämlic auch so gemacht).
In der vorlesung haben wir ja "randomized quicksort" mit einem zufallspiovt element gemacht, da wurde dass auch so gemacht. also ist das kein problem wenn wir es so machen

SebFreutel
Computerversteher
Computerversteher
Beiträge: 317
Registriert: 30. Okt 2006 21:54

Re: Quicksort B - erlaubt zu tauschen?

Beitrag von SebFreutel »

Klar, das ist erlaubt.
Du solltest dir nur (sowieso) Gedanken machen und erklären können, wie sich das positiv oder negativ auf die Performance auswirkt (und ggf. andere Lösungen in Erwägung ziehen, wenn es bessere gibt, sie dir einfallen und - hinsichtlich Datums - du noch die Zeit dazu hast)

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

Re: Quicksort B - erlaubt zu tauschen?

Beitrag von Wambolo »

Die Frage würde ich gleich mal ausweiten, wenn ich mir das mittlere Element aus dreien suche, dann kenne ich ja auch das kleinste und das größte. Wenn ich jetzt nur das mittlere auf die Pivotposition stelle(also austausche), dann bekomme ich bei meinem Algorithmus für QuicksortB File 3 6603 Lesezugriffe.

Tausche ich das mittlere auf Pivotposition, das höchste auf die letzte Position und das niedrigste auf die mittlere Position im Array, dann reduzieren sich die zugriffe auf 4000. Bei der unsortierten und der aufsteigend sortierten Liste ändern sich die Werte kaum.

Darf ich so einen Tausch vornehmen oder wird dadurch das Quicksort Prinzip untergraben?
Interpreter/Parser reported on Nov 12, 2008 8:30:04 PM:
Number too big (102 > 42).

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Re: Quicksort B - erlaubt zu tauschen?

Beitrag von mantra »

Wambolo hat geschrieben:Tausche ich das mittlere auf Pivotposition, das höchste auf die letzte Position und das niedrigste auf die mittlere Position im Array, dann reduzieren sich die zugriffe auf 4000. Bei der unsortierten und der aufsteigend sortierten Liste ändern sich die Werte kaum.

Darf ich so einen Tausch vornehmen oder wird dadurch das Quicksort Prinzip untergraben?
Prinzipiell ist das noch erlaubt. Ich würde mir nur überlegen, ob ihr euch wirklich so viele Tricksereien in den Code einbauen wollt. Je mehr Schnörkel ihr macht, desto mehr habt ihr zu erklären.
Ein einfacher Code mit wenig Zauberei ist schneller testiert. Und das schont unser aller Nerven ;)

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

Re: Quicksort B - erlaubt zu tauschen?

Beitrag von Wambolo »

...da ist natürlich was dran
Interpreter/Parser reported on Nov 12, 2008 8:30:04 PM:
Number too big (102 > 42).

Antworten

Zurück zu „Archiv“