-
        

Seite 1 von 2 12 LetzteLetzte
Ergebnis 1 bis 10 von 11

Thema: Quicksort Abbruchbedingung ?

  1. #1
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    05.11.2007
    Ort
    Berlin
    Beiträge
    526

    Quicksort Abbruchbedingung ?

    Anzeige

    Hallo zusammen,
    ich habe folgenden Code für einen Quicksort Algo... gefunden.

    Code:
    void quick_sort(int *a, int n)
    {
      int p = a[n / 2];
      int *l = a;
      int *r = a + n -1;
      
      while (l <= r) 
      {
         while (*l < p) l++;
         while (*r > p) r--;
         if (l <= r)
         {
           int t = *l;
           *l++ = *r;
           *r-- = t;
         }
      }
      quick_sort(a, r - a + 1);
      quick_sort(a, r + n - l); 
    }
    Ich verstehe aber nicht, wo hier die Abbruchbedingungen sind.
    Das Array hat ja eine gewisse Größe (Anzahl von Elementen) worauf der übergebene int* a zeigt. die Zeile
    while(*l < p) l++
    kann doch meiner Meinung nach unendlich, zumindest bis weit über das Array Ende hinaus laufen. Es wird doch nur abgefragt, ob der Wert, worauf der Zeiger l zeigt kleiner ist als der Wert p..... ebenso die Zeile
    while(*r >p) r--
    Oder habe ich hier etwas nicht richtig verstanden ?
    für eine Info wäre ich Euch dankbar.
    Siro

  2. #2
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    19.05.2005
    Ort
    Berlin
    Beiträge
    316
    Dieser Algorithmus wird niemal terminieren.
    Die Aufrufe von quick_sort() sind an keinerlei Bedingungen geknüpft. Es gibt auch keine vorzeitigen returns.

  3. #3
    Erfahrener Benutzer Roboter Experte Avatar von sternst
    Registriert seit
    07.07.2008
    Beiträge
    672
    Zitat Zitat von Siro Beitrag anzeigen
    die Zeile
    while(*l < p) l++
    kann doch meiner Meinung nach unendlich, zumindest bis weit über das Array Ende hinaus laufen.
    Nein, denn l trifft ja irgendwann mal auf das Element, mit dem p initialisiert wurde. Für r gilt das Gleiche.

    Der Einwand von lokirobotics ist aber berechtigt. Insgesamt kann das so nicht funktionieren. Vielleicht falsch abgetippt?
    MfG
    Stefan

  4. #4
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    05.11.2007
    Ort
    Berlin
    Beiträge
    526
    zu "lokirobotics" : Habs probiert, gibt einen Stackoverflow......
    Und "sternst" geb ich auch recht. "l" und "r" treffen irgendwann den wert von "p".
    Habe mich grad mal intesiver damit auseinandergesetzt.
    Habe ein (weils mir leichter fällt) Pascal (Delphi) Programm geschrieben, welches nun einwandfrei läuft.
    Nun habe ich es nach "C" konvertiert. Da ich doch noch erhebliche Probleme mit "C" habe, wird mir dabei sicher ein Fehler unterlaufen sein. Den find ich nur irgendwie nicht.
    Könnt Ihr da mal drauf schauen, was ich dort falsch gemacht habe. Das C-Programm bekommt einen Stackoverflow.....

    Zunächst meine funktionierende Pascal-Variante:

    Code:
    const ar:Array[0..4] of Integer = (5,4,3,2,1);
    
    procedure QSort(lo,hi:Integer);
    var left,right,mid,tmp:Integer;
    begin
      left  := lo;
      right := hi;
      mid   := ar[(lo+hi) DIV 2];
      repeat
        while (ar[left]  < mid) do inc(left);
        while (ar[right] > mid) do dec(right);
        if left <= right then begin
          tmp := ar[left];
          ar[left]  := ar[right];
          ar[right] := tmp;
          inc(left);
          dec(right);
        end;
      until left > right;
      if right > lo then QSort(lo,right);
      if left  < hi then QSort(left,hi);
    end;
    
    begin
      QSort(0,sizeof(ar) DIV sizeof(ar[0]) -1);
    end.
    und nun mein anscheinend fasch konvertiertes "C" Programm

    Code:
    U16 ar[5] = {5,4,3,2,1};
    
    void QSort(U16 lo, U16 hi)
    { U16 left,right,mid,tmp;
      left  = lo; 
      right = hi;
      mid   = ar[(lo+hi)/2];
      do 
      {    
         while (ar[left]  < mid) left++; 
         while (ar[right] > mid) right--;
         if (left <= right)
         {
           tmp       = ar[left];
           ar[left]  = ar[right];
           ar[right] = tmp;
           left++; 
           right--;
         }
      } while (left <= right);
      if (right > lo) QSort(lo,   right);
      if (left  < hi) QSort(left, hi);
    }
    
    
    int main(void)
    { 
      QSort(0,sizeof(ar) / sizeof(ar[0]) -1);
    }
    Ich danke euch,
    Siro
    Geändert von Siro (29.04.2011 um 15:41 Uhr)

  5. #5
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    05.11.2007
    Ort
    Berlin
    Beiträge
    526
    Ich habe mein Problem gefunden. Habe es selbst verursacht weil ich komplett mit unsigned Werten U16 gearbeitet habe.
    Das geht hier schief. Ich muss Signed bzw. "int" benutzen. hab ich in Pascal ja auch getan.
    Der Wert "right" landete bei -1 (also 65535) und dann ging natürlich die Abfrage falsch.
    oder ich schreibe hinter der left++ Zeile, im unterem Abschnitt if (right) right--; dann geht es auch mit unsigned Werten.
    Hier noch mal die korrigierte Version:

    Code:
    U16 ar[5] = {5,4,3,2,1};
    
    void QSort(U16 lo, U16 hi)
    { U16 left,right,mid,tmp;
      left  = lo; 
      right = hi;
      mid   = ar[(lo+hi)/2];
      do 
      {    
         while (ar[left]  < mid) left++; 
         while (ar[right] > mid) right--;
         if (left <= right)
         {
           tmp       = ar[left];
           ar[left]  = ar[right];
           ar[right] = tmp;
           left++; 
           if (right) right--;
         }
      } while (left <= right);
      if (right > lo) QSort(lo,   right);
      if (left  < hi) QSort(left, hi);
    }
    
    
    int main(void)
    { 
      QSort(0,sizeof(ar) / sizeof(ar[0]) -1);
    }
    Ich glaub jetzt hab ich alle Probleme gelöst, wird ja auch Zeit fürs Wochenende.
    Siro
    Geändert von Siro (29.04.2011 um 16:12 Uhr)

  6. #6
    Erfahrener Benutzer Robotik Einstein Avatar von SprinterSB
    Registriert seit
    09.06.2005
    Ort
    An der Saar
    Beiträge
    2.801
    Hi Siro. Es gibt ein qsort in der avr-libc. Warum also das Rad neu erfinden?
    Disclaimer: none. Sue me.

  7. #7
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    19.05.2005
    Ort
    Berlin
    Beiträge
    316
    Zitat Zitat von SprinterSB Beitrag anzeigen
    Hi Siro. Es gibt ein qsort in der avr-libc. Warum also das Rad neu erfinden?
    Weil es so gut wie alles, was es hier gemacht wird, schon fertig gibt. Wozu also überhaupt noch was selber machen?
    Ich find solche Kommentare in einem Forum wie diesen mehr als sinnlos.

    Siro will wahrscheinlich was lernen und das tut man nicht, wenn man Fertigkomponenten benutzt.

  8. #8
    Erfahrener Benutzer Robotik Einstein Avatar von Felix G
    Registriert seit
    29.06.2004
    Ort
    49°32'N 8°40'E
    Alter
    34
    Beiträge
    1.780
    Es gibt fast alles schon irgendwo fertig, das stimmt...

    Aber qsort gibt es nicht einfach nur irgendwo, sondern es ist Teil der C-Standardbibliothek, was vielen nicht bewusst ist. Von deinem Standpunkt aus betrachtet müsste man also auch z.B. die Existenz von Funktionen wie sprintf "geheimhalten", weil es ja sein könte, daß das Jemand lieber selber implementieren möchte um etwas dabei zu lernen.


    Ich denke es sollte Jedem selbst überlassen sein, ob er Fertigkomponenten nutzen, oder lieber etwas eigenes implementieren möchte.
    So viele Treppen und so wenig Zeit!

  9. #9
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    19.05.2005
    Ort
    Berlin
    Beiträge
    316
    Du hast meinen Standpunkt missverstanden! Dein letzter Absatz ist genau das, was ich meinte. Jeder sollte seine Projekte so umsetzen, wie er möchte.
    Man muss auch nichts geheimhalten. Ich kann ja auch eine fremde Implementierung als Grundlage für eine Eigene nehmen.
    Ich find halt diese "Warum das Rad neu erfinden"-Aussagen schwachsinnig.

    Jaa, mein letzter Satz ist etwas übertrieben gewesen, natürlich lernt man auch, wenn man Fertigkomponenten einsetzt. Mir ging es in dem Fall nur darum, dass man die Funktionsweise des QSort nicht sehr gut mitbekommt, wenn man nur nen Aufruf einer fertigen Funktion tätigt. War etwas missverständlich geschrieben, stimmt.

    MfG

  10. #10
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    05.11.2007
    Ort
    Berlin
    Beiträge
    526
    zu SprinterSB
    ich wuste das nicht, daß es die funktion in der standard lib gibt.
    unabhängig davon wollte ich sie aber selbst implementieren.

    zu Felix G
    gut erkannt, ich benutze z.B. auch KEIN printf, habe mir was eigenes geschrieben, da mir der Source Code nicht zur Verfügung steht und die mitgelieferte LIB wesentlich zu viel Speicher dafür "verbrät".....

    Klar gibt es fertige Algo-"Rhythmen". Lernen und Verständnis steht bei mir aber im Vordergrund.
    Wenn es alles schon fertig gibt, bräuchte ich meine Software erst garnicht schreiben, die gibt es sicher auch schon Spass muss sein.

    Durch die eigene Implementierung (Grundlage war aber "abgeguckt") hab ich die Vorgehensweise von QSort tatsächlich verstanden. Hat zwar einen Tag gedauert aber es hat sich gelohnt. Ich hab mir mal den Aufruf der Standardfunktion QSort angesehen. Die Idee ist eigentlich nicht schlecht. Hier muss man also eine eigene Funktion schreiben, welche 2 Werte (oder was auch immer) vergleicht und das Resultat zurück liefert. Der eigentlich Sortieralgo. ist damit universell. Ist echt zu überlegen, ob ich das nicht auch gleich so mache.

    Danke Euch für die Infos.
    Siro

Seite 1 von 2 12 LetzteLetzte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •