Quicksort-Notation Härder - Wie ist das zu verstehen???

k_b
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 213
Registriert: 15. Mär 2009 12:06

Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von k_b »

Hallo,

ich verstehe gerade die Notation wie Härder den Quicksort aufschreibt nicht. Kann mir das jemand anhand des Beispiels im Härder-Skript erklären? Ein Bild des Beispiels ist auch nochmal im Anhang meines beitrags. Was mich am meisten verwirrt ist, welche Schritte muss ich aufschreiben und welche lasse ich weg, d.h. ich schreibe ja nicht jeden Einzelschritt des Sortierens auf, sondern doch eher die einzenen Pivot-Elemente und die sortierten Teillisten die entstehen und wieder die neuen Pivotelemente usw. rekursiv weiter auf jede Teilliste bis es ichts mehr zu sortieren gibt - ich also eine einelementige Liste habe? Warum schreibe ich die selbe Zeile 2-mal hin nur etwas vesetzt?


Danke schonmal :)

VMann
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 16. Apr 2009 11:51

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von VMann »

Muss ich das Pivot-Element wie in dem Beispiel nochmal in eine Teilliste aufnehmen oder darf ich es zwischen den zwei Teillisten stehen lassen?
Computer tun nicht das, was du von ihnen willst, sie tun das, was du ihnen sagst.

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von Demmi »

k_b hat geschrieben:Warum schreibe ich die selbe Zeile 2-mal hin nur etwas vesetzt?
Das dient zur Visualisierung der Teillisten (im Skript in Durchgang 1) bzw. um zu zeigen, welcher Teil schon fertig sortiert ist (so wie die späteren Durchgänge).
VMann hat geschrieben:Muss ich das Pivot-Element wie in dem Beispiel nochmal in eine Teilliste aufnehmen oder darf ich es zwischen den zwei Teillisten stehen lassen?
Das Pivot-Element muss auf jeden Fall drin bleiben, es wird ja im weiteren Verlauf mit sortiert. Also bitte an die Darstellung im Härder-Skript halten. Und zusätzlich i und j nicht vergessen, die müssen auch in jedem Durchgang reingezeichnet werden, so wie in der Gruppenübung.
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von mister_tt »

Demmi hat geschrieben:Und zusätzlich i und j nicht vergessen, die müssen auch in jedem Durchgang reingezeichnet werden, so wie in der Gruppenübung.
Wie soll man in die Notation von Härder noch die Zeiger einbauen? Die machen da doch gar keinen Sinn, da man bei der Härder-Notation ja nur einen kompletten Quicksort-Durchlauf zeichnet und damit die fertigen Teillisten... Die Zeiger machen nur Sinn, wenn man die Konstruktion der Teillisten schrittweise ausführt (wie in der Musterlösung).

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von Demmi »

Stimmt schon was du sagst. Du sollst i und j jeweils immer nur im Endzustand mit reinzeichnen, also quasi wo sie sich treffen.
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von daniel_b »

Ich verstehs immernoch nich..

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von mister_tt »

Ok einfaches Beispiel mit der Härder-Notation...

Zu sortieren: 100 25 80 50 90

Code: Alles auswählen

p = 100 (Größeres des ersten und letzten Elements)
          j     i  (Zeigerposition, bei der abgebrochen wird)
90 25 80 50 | 100  (erster Durchlauf von Quicksort)
90 25 80 50 | fertig (nochmal hinschreiben, warum auch immer)
usw.

Richtig? Anders gemeint?

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von ivoch »

mister_tt hat geschrieben:Ok einfaches Beispiel mit der Härder-Notation...

Zu sortieren: 100 25 80 50 90

Code: Alles auswählen

p = 100 (Größeres des ersten und letzten Elements)
          j     i  (Zeigerposition, bei der abgebrochen wird)
90 25 80 50 | 100  (erster Durchlauf von Quicksort)
90 25 80 50 | fertig (nochmal hinschreiben, warum auch immer)
usw.

Richtig? Anders gemeint?
Genau.

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von mister_tt »

bescheuert...

linn
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 15. Okt 2008 21:16

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von linn »

Bricht der Algorithmus auch ab, wenn j<i ist? in den folien steht ja do {} while (i!=j),
was aber z.B. bei 1 2 3 mit 3 als pivot (grösseres zwischen ganz links und ganz rechts) nicht funktionieren würde:

while (a < a[pivot}) i++;
while (a[j] >= a[pivot]) j--;

jetzt wären die Zeiger so
1 2 3
__j_i
und da (i!=j) würde er im nächsten Schleifendurchgang 2 mit 3 vertauschen und mit i die liste verlassen.

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von bruse »

Ja, eine korrekte Implementierung testet einfach ab, ob i >= j.

Übrigens wird auch das Pivotelement in einer richtigen Implementierung von Quicksort NICHT neu mitsortiert. Wenn man es nach dem i-j-Zeiger-Gefuddel genau in die Mitte (zwischen den beiden Teilen, < p und >= p) tauscht (das geht z.B. wenn man das Pivot vorher ans Ende getauscht hatte und rechts >= Pivot gilt), dann braucht es ja nicht mehr sortiert werden, weil es ja schon an der richtigen Stelle steht.

Die Java-Implementierung in den Folien macht es korrekt, die davor leider nicht.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

dumbo2
Neuling
Neuling
Beiträge: 9
Registriert: 20. Mai 2009 20:05

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von dumbo2 »

Hallo zusammen,

ich komm irgendwie nicht richtig weiter momentan.

Ich hab folgende Folge: 50(i) | 61 | 55 | 47(j) p=50

Ich gehe nun die Elemente von links durch, bis ich ein Element i gefunden hab, für dass gilt p <= i.
Das wäre nach meinem Verständnis nun die 50, also gleich das erste Element.
Von rechts gehe ich die Folge durch und suche ein Element j, für das gilt j < p.
Auch hier ist es das erste Element, also 47.
Nun überprüfe ich die Bedingung fürs Austauschen oder Abbrechen:
wenn i < j tausche ich aus,
wenn i > j stoppe ich.

Da aber i > j in diesem Fall, muss ich stoppen und hab eine nicht aufsteigend sortierte Liste, welche ich eigentlich brauche.
Ich finde auch weder im Härder- noch im Vorlesungsskript etwas, wie ich in diesem Fall weitermachen soll.

Also die genaue Frage wäre dann, wie verhalte ich mich, wenn das erste linke Element >= p und das erste rechte Element < p ist.

Wäre sehr dankbar für eine Erklärung.

Gruß Olli

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von ivoch »

dumbo2 hat geschrieben:wenn i < j tausche ich aus,
wenn i > j stoppe ich.

Da aber i > j in diesem Fall, muss ich stoppen und hab eine nicht aufsteigend sortierte Liste, welche ich eigentlich brauche.
Ich finde auch weder im Härder- noch im Vorlesungsskript etwas, wie ich in diesem Fall weitermachen soll.
Sagen wir mal deine Liste mit Zahlen ist in einem Array "arr" gespeichert. "Wenn i>j" bedeutet hier genau das: i>j, und NICHT arr>arr[j]. Merkst du den Unterschied?

Ausserdem, solltest du den Pivot nicht in der jeweils zu sortierende Teilliste miteinbeziehen - siehe die Folien, Seite 55.

h4ck4
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 18. Mai 2009 20:50
Kontaktdaten:

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von h4ck4 »

Sorry...muss aber ma ne dumme Frage stellen, da hier die Rede vom Härder Skript ist:
Das Härder Skript kann man ja im Copies kaufen...wo ist denn Copies? Kam zwar immer sehr gut mit den Folien aus der Vorlesung und Literaturmaterial zurecht...müsst mir aber ja mal trotzdem das Skript zu legen :oops:

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Re: Quicksort-Notation Härder - Wie ist das zu verstehen???

Beitrag von Osterlaus »

h4ck4 hat geschrieben:Sorry...muss aber ma ne dumme Frage stellen, da hier die Rede vom Härder Skript ist:
Das Härder Skript kann man ja im Copies kaufen...wo ist denn Copies? Kam zwar immer sehr gut mit den Folien aus der Vorlesung und Literaturmaterial zurecht...müsst mir aber ja mal trotzdem das Skript zu legen :oops:
Das hätte dir sogar die Forensuche gesagt ;) Holzstr. 11, gegenüber vom Liebighaus.

Antworten

Zurück zu „Archiv“