Results 1 to 12 of 12

Thread: Aufgabe 13

  1. #1
    Master
    Join Date
    Dec 2007
    Location
    Vienna
    Posts
    106
    Thanks
    6
    Thanked 2 Times in 2 Posts

    Aufgabe 13

    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?
    Mac Book Pro - what else

  2. #2
    Master
    Join Date
    Dec 2007
    Location
    Vienna
    Posts
    106
    Thanks
    6
    Thanked 2 Times in 2 Posts
    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)
    Mac Book Pro - what else

  3. #3
    Dipl.Ing
    Join Date
    May 2010
    Posts
    1,580
    Thanks
    179
    Thanked 394 Times in 287 Posts
    Es schaut so aus, als ob du im letzten Zusammenfügenschritt nicht noch mal sortierst...

  4. #4
    Hero
    Join Date
    Oct 2011
    Location
    Guntramsdorf
    Posts
    218
    Thanks
    14
    Thanked 52 Times in 35 Posts
    EDIT: Habe das selbe Problem mit 18 und 19.. :S
    Last edited by neptunez; 04-04-2012 at 15:50.

  5. #5
    Master skYeYe's Avatar
    Join Date
    Feb 2008
    Location
    Vienna
    Posts
    120
    Thanks
    26
    Thanked 5 Times in 4 Posts
    @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
    Last edited by skYeYe; 05-04-2012 at 01:19.
    ComputerBase sysProfile
    H.Lesch@alpha-Centauri
    Wer lesen kann ist klar im Vorteil

  6. #6
    Dipl.Ing yrucrem's Avatar
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Quote Originally Posted by skYeYe View Post
    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.
    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  7. #7
    Master skYeYe's Avatar
    Join Date
    Feb 2008
    Location
    Vienna
    Posts
    120
    Thanks
    26
    Thanked 5 Times in 4 Posts
    @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?)
    ComputerBase sysProfile
    H.Lesch@alpha-Centauri
    Wer lesen kann ist klar im Vorteil

  8. #8
    Master
    Join Date
    Nov 2010
    Posts
    104
    Thanks
    29
    Thanked 23 Times in 18 Posts
    Quote Originally Posted by skYeYe View Post
    @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
    Last edited by Tobmaster; 11-04-2012 at 14:02.

  9. The Following User Says Thank You to Tobmaster For This Useful Post:


  10. #9
    Master EsseX07's Avatar
    Join Date
    Sep 2011
    Posts
    151
    Thanks
    29
    Thanked 11 Times in 9 Posts
    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 ^^...
    "Programming is similar to sex. If you make a mistake, you have to support it for the rest of your life."

  11. The Following User Says Thank You to EsseX07 For This Useful Post:


  12. #10
    Principal
    Join Date
    Oct 2011
    Posts
    96
    Thanks
    2
    Thanked 12 Times in 8 Posts
    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?

  13. #11
    Hero Salmir's Avatar
    Join Date
    Mar 2010
    Location
    elf-60
    Posts
    195
    Thanks
    20
    Thanked 18 Times in 18 Posts
    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
    Die Ewigkeit dauert verdammt lange, vorallem gegen Ende

  14. #12
    Master skYeYe's Avatar
    Join Date
    Feb 2008
    Location
    Vienna
    Posts
    120
    Thanks
    26
    Thanked 5 Times in 4 Posts
    @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
    Last edited by skYeYe; 17-04-2012 at 01:19.
    ComputerBase sysProfile
    H.Lesch@alpha-Centauri
    Wer lesen kann ist klar im Vorteil

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •