Announcement

Collapse
No announcement yet.

Aufgabe 13

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new 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
    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

    Comment


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

      Comment


      • #4
        EDIT: Habe das selbe Problem mit 18 und 19.. :S
        Last edited by neptunez; 04-04-2012, 14:50.

        Comment


        • #5
          @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, 00:19.
          ComputerBase sysProfile
          H.Lesch@alpha-Centauri
          Wer lesen kann ist klar im Vorteil

          Comment


          • #6
            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!

            Comment


            • #7
              @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

              Comment


              • #8
                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, 13:02.

                Comment


                • #9
                  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."

                  Comment


                  • #10
                    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?
                    EVC-Tutorin

                    Comment


                    • #11
                      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

                      Comment


                      • #12
                        @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, 00:19.
                        ComputerBase sysProfile
                        H.Lesch@alpha-Centauri
                        Wer lesen kann ist klar im Vorteil

                        Comment

                        Working...
                        X