Wo liegt der Fehler bei Quicksort (c++)

[Gast]

Hi,
hier ist mein Code:

void TForm1::quicksort(int feld[],int begin,int end)
{
int n=(end-begin)/2;

int tmp;
int old_begin=begin;
int old_end=end;
while(begin<=end)
{
while(feld[begin]<feld[n])
{
begin++;

}
while(feld[end]>feld[n])
{
end--;
}

if(begin<=end)
{
tmp=feld[end];
feld[end]=feld[begin];
feld[begin]=tmp;
begin++;
end--;

}

}
if(old_begin<end)
{
quicksort(feld,old_begin,end);


}
if(begin<old_end)
{
quicksort(feld,begin,old_end);
}

}

Wo liegt mein Fehler bei der Implementierung?
Es kommt immer ein Stack Overflow, wenn ich die Methode so aufrufe:

int feld[6];
feld[0]=2;
feld[1]=1;
feld[2]=4;
feld[3]=2;
feld[4]=6;
feld[5]=5;
this->quicksort(feld,0,6);

[Einfachkrank]

Wäre eine spontane Überlegung, aber sollte end im Aufruf
this->quicksort(feld,0,6);
nicht 5 sein, da der Array zwar 6 Felder hat, aber die von 0 bis 5 gehn...

[Gast]

daran liegt das leider nicht.

[darph]

Moment, du erzeugst ein Array mit 6 Feldern, sortierst aber die Zahlen 0-6, also 7 Zahlen insgesamt...

versucht's mal mit int feld[7];aber immer noch mit this->quicksort(feld,0,6);

[Trap]

Ich hasse Quicksort implementieren, da reicht ein winziger Fehler damit es nichtmehr funktioniert.

An deiner Stelle würde ich entweder das aus der Standardbibliothek nehmen, oder es aus http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf abschreiben.

[Gast]

So den Stackoverflow habe ich weg

void TForm1::quicksort(int feld[],int begin,int end)
{
int n=(end-begin)/2;

int tmp;
int old_begin=begin;
int old_end=end;
do
{
while(feld[begin]<feld[n])
{
begin++;

}
while(feld[end]>feld[n])
{
end--;
}
if(begin<=end)
{

tmp=feld[begin];
feld[begin]=feld[end];
feld[end]=tmp;

}
begin++;
end--;

}
while(begin<end);


if(old_begin<end)
{

quicksort(feld,old_begin,end);
}


if(old_end>begin)
{
quicksort(feld,begin,old_end);
}

}

Das einzige Problem was ich noch habe, ist das bei

feld[0]=1;
feld[1]=45;
feld[2]=2;
feld[3]=6;
feld[4]=434;
feld[5]=-1;

Die 434 wird nicht richtig sortiert,sondern sie bleibt immer auf dem falschen platz.Wenn ich stattdessen -33 eintrage wird der Wert richtig sortiert.
Die restlichen Zahlen werden immer richtig sortiert.

[Aqualon]

Dein Algorithmus scheint auch sonst noch einen Fehler zu enthalten. Folgende Zahlenfolge sortiert er nämlich nur soweit, dass die 2 und die 45 ausgetauscht werden:
feld[0]=1;
feld[1]=45;
feld[2]=2;
feld[3]=6;
feld[4]=10;
feld[5]=434;
Aqua

[Gast]

Mit der Variante klappt es nun.

void TForm1::quicksort(int feld[],int begin,int end)
{
if(end>begin)
{

int old_begin=begin;int old_end=end;int tmp;
begin--;
for(;;)
{
while(feld[++begin]<feld[old_end]);
while(feld[--end]>feld[old_end]);
if(begin>=end)
{ break;
}

tmp=feld[begin]; feld[begin]=feld[end]; feld[end]=tmp;
}
tmp=feld[begin]; feld[begin]=feld[old_end]; feld[old_end]=tmp;

quicksort(feld,old_begin,begin-1);
quicksort(feld,begin+1,old_end);

}
}

[Coda]

Ich hab mal nen QuickSort für doppelt verlinkte Listen geschrieben. Das war noch viel schlimmer ;)