Aufgabe 13

[schakeu07]

Hi, hat wer die Aufgabe schon. Sollte eigentlich imho simpel sein - habe nur in Zeile 5 und Zeile 8 bei Partition Methode / Algorithmus die Symbole umgedreht auf <= und >= ... der Algorithmus sortiert dann auch brav nach Schema - nur komm ich am Ende auf folgende Zahlenfolge und habs jetzt mittlerweile mind. ein dutzend mal durchgesehen aber den Fehler nicht gefunden :/

<73, 55, 34, 33, 18, 19, 5, 4, 2, 1>

Bekomme den 18er nicht mehr hinter den 19er :/

Hat noch wer das Problem bzw eine Lösung gefunden ? Das Verdrehen der Vergleichsoperatoren sollte ja stimmen oder?

[schakeu07]

lustig - wenn ich s aufsteigend sortier - habe ich dann <1,2,4,5,19,18,33,34,55,73>

Wo zum Geier mache ich da den einen falschen Schritt :/

(dh das verdrehen der vergleichsoperatoren scheint zu stimmen - immerhin)

[DarkInferno]

Es schaut so aus, als ob du im letzten Zusammenfügenschritt nicht noch mal sortierst...

[neptunez]

EDIT: Habe das selbe Problem mit 18 und 19.. :S

[skYeYe]

@schakeu07 & neptunez
Habe das selbe Problem. Grundsätzlich würde ich schakeu07 zustimmen: einfach die >= (Zeile 5) und <= (Zeile 8) Operatoren umtauschen in <= und >=. Am Ende sieht es dann so aus bei mir: |73 55 34 33 18 19 5 4 2 1|, 18 und 19 müssen noch sortiert werden, der Rest ist fertig. i = l - 1; l = 1, dh i = 0 und in der Schleife wird es dann inkrementiert (Zeile 4) und wird zu i = 1, dh A[1] <= x, dh 18 <= 19 ok, aber jetzt kommt das Problem, denn j = r und r = 2, j = j-1 in der Schleife (Zeile 7), dh j = 1, daraus folgt A[1] >= x, dh 18 >= 19 FEHLER! er hat eben nicht verglichen ob 19 größer 18 ist... oder übersehe ich da was? mhm... vll ist es auch schon so spät^^, aber um das Problem zu umgehen, würde ich folgendes Vorschlagen: Wenn das Array aus zwei Elementen besteht soll einfach überprüft werden ob das linke kleiner dem rechten ist, in dem Fall die Elemente tauschen, ansonsten soll es gleich bleiben. Was sagt ihr dazu?

Aus den vorigen Semestern konnten die noch keine Fehler feststellen: BSP 37 LINK 1 und LINK 2

[yrucrem]

l = 1 [...] r = 2

Eigentlich ist i = 5 und j = 6 (bzw. 4 und 5, je nachdem ob die Arrayindices bei 1 oder 0 beginnen), aber das ist zugegebenermaßen hier nicht so wichtig.

[...] j = 1, daraus folgt A[1] >= x, dh 18 >= 19 FEHLER! er hat eben nicht verglichen ob 19 größer 18 ist

Warum ist es ein Fehler, wenn A[j] >= x nicht erfüllt ist? Der Algorithmus überprüft genau an dieser Stelle ob 19 > 18 und stellt fest, dass dem so ist. Jetzt möchte er das j weiter nach links schieben, was nicht geht, weil die Folge da schon aus ist. Außerdem würde das j in den Bereich kommen, den eh das i schon abgegrast hat. Er bricht diese Schleife also wegen j <= i ab. Nach der Schleife, die das j bestimmt, gilt j = i, also wird sinnvollerweise nicht A[i] mit A[j] vertauscht, sondern er setzt gleich das Pivotelement an die richtige Stelle indem er A[i] =18 mit A[r] =19 vertauscht.

[skYeYe]

@yrucrem
thx 4 help, aber ich steh jetzt ein bissl auf der Leitung, was es den Pseudocode - Algorithmus 6 und 7 betrifft. Also nehmen wir die Folge her: {5, 18, 33, 4, 55, 2, 1, 73, 19, 34}, so habe ich folgendes definiert: array A[0]=5, dh (klein L) l = 0, und A[9]=34, dh r = 9; x = A[r].key also x = 34. p = Partition(A,l,r,x), dh Partition(A,0,9,34). Jetzt steht im Algorithmus 7 folgendes: i = l-1, dh i = -1 und j=r, dh j=9; while(i <= j) {while(A[i].key >= x){...}}. Wie soll das gehen, wenn A[-1] nicht existiert?
Danke schon mal! (handelt es sich hier um eine do-while Schleife?)

[Tobmaster]

@yrucrem
thx 4 help, aber ich steh jetzt ein bissl auf der Leitung, was es den Pseudocode - Algorithmus 6 und 7 betrifft. Also nehmen wir die Folge her: {5, 18, 33, 4, 55, 2, 1, 73, 19, 34}, so habe ich folgendes definiert: array A[0]=5, dh (klein L) l = 0, und A[9]=34, dh r = 9; x = A[r].key also x = 34. p = Partition(A,l,r,x), dh Partition(A,0,9,34). Jetzt steht im Algorithmus 7 folgendes: i = l-1, dh i = -1 und j=r, dh j=9; while(i <= j) {while(A[i].key >= x){...}}. Wie soll das gehen, wenn A[-1] nicht existiert?
Danke schon mal! (handelt es sich hier um eine do-while Schleife?)

Ja, hier musst du eine do-While Schleife verwenden. Also in der Form:
do{
i=i+1;
while(A[i].key<x)

Bei einer Do-While-Schleife werden zuerst die Anweisungen im do-Teil ausgeführt, danach wird erst die Abbruch-Bedingung überprüft -> i=-1 wird im do-Teil auf 0 erhöht, und dieser Index existiert ja.

Edit: Außerdem musst du beachten das im Pseudocode die Schleife mit wiederhole ..... bis A[i].key>=x angegeben ist -> Schleife wird solange A[i].key<x ist wiederholt

[EsseX07]

habs jetzt in java nach programmiert und es funktioniert so
zeile 5: bis A[i].key ≤ x;
zeile 8: bis j ≤ i oder A[j].key ≥ x;
18 und 19 sind am ende in der korrekten reihenfolge

pm falls jemand das programm haben möchte ^^...

[Chocookie]

könnte mir jemand mal beim nachvollziehen von Quicksort helfen? =/
warums anders herum sortiert, wenn man die Bedinungen umdreht ist mir klar, allerdings versteh ich nicht ganz was passiert, wenn ich die Folge so weit sortiert hab:
<5,18,33,4,55,2,1,73,19,34>
...
<73,55|34|4,18,2,1,5,19,33>
34 war ja vorher Pivot-Element, also wird jetzt mit der linken Teilfolge weitergemacht. die besteht aber nur mehr aus 2 Elementen, 55 das neue Pivotelement, i links von 73 und j auf 73... versteh ich das richtig dass da nichts passiert, oder wird 73 mit 55 vertauscht, weil i+1 mit dem Pivotelement vertauscht wird, egal was passiert?

[Salmir]

Also bei mir kommt jetzt (ich glaube nach der 3. Rekursion von _Quicksort(A,l,r)_): <73,55,34,33,18,2,1,5,19,4>... danach <73,55,34,33,18,19,5,4,2,1> raus.
Da wir im Algorithmus 6, nachdem p returned wurde, Quicksort(A,l,p-1); ausführen, wird doch die linke Seite von A, also <18,19,5> (Grenzen 5-7)... i wandert von 18 bis 5, j-- wird einmal ausgeführt, es wird nichts vertauscht (da i > j ist) -> p = 7 (Index 7, mit .key = 5).
Jetzt wird <18,19> überprüft (Grenzen sind l=5, p-1=6), i bleibt bei 18 hängen, j-- (Abbruchbedingung j kleinergleich i erreicht) -> Zeile 14: Vertausche A[i] und A[r], A[5]=18 & A[6]=19 -> richtige Reihenfolge...

lg

[skYeYe]

@Salmir
i und j haben beide den Wert 5 (i = l-1 = 4, dann i++, dann i = 5, dann 18 <= 19 ok, j = r = 6, dann j--, dh j = 5, dann j <= i (5<=5) = while-Schleifenbedingung [Zeile 8] erfüllt, bis [Zeile 12] i >= j, wieder Schleifendurchlauf erfüllt, dann falls i < j, dh 5 < 5, dann vertauschen - es kommt aber nicht dazu, weil 5 !< 5... A[i] und A[r] vertauschen, wobei i = 5 und r = 6, dadurch neu2 = A[r]; A[r] = A[i]; A[i] = neu2; und jetzt ist die folge <19, 18>
Habe auch ne Menge Zeit verbracht mit diesem Quicksortalgorithmus