Quicksort Abbruchbedingung ?

[Siro]

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

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

[lokirobotics]

Dieser Algorithmus wird niemal terminieren.
Die Aufrufe von quick_sort() sind an keinerlei Bedingungen geknüpft. Es gibt auch keine vorzeitigen returns.

[sternst]

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?

[Siro]

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:

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

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

[Siro]

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:

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

[SprinterSB]

Hi Siro. Es gibt ein qsort in der avr-libc. Warum also das Rad neu erfinden?

[lokirobotics]

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.