Probleme mit Quicksort

[Uwe Richtsteig]

Hallo!

in dem farbig angelegent Block, gibt es die drei Alternativen, die die linken und rechten Teile in einer Wertereihe fArray im zuge des <b>QuickSort</b>-Algorhytmus bearbeiten. Alle übrigen Programmteile werden mit jedem einzelnen Alternativabschnitt unverändert implemiert.

Nur die Alternative 1 (grün) führt zur ordnungsgemäßen Sortierung nach dem QuickSort-Verfahren.<hr width=60%><pre>float fArray[]={-1, 30, 82, 90, 56, 17, 95, 15, 48, 26, 4, 58, 71};
int maxN=sizeof(fArray)/sizeof(float);
//------------------------------
void QuickSortA(int sortcol, int xa, int xe);
void qusortA(int sortcol, int left, int right);
bool IsLessThen(int sortcol, int vleft, int vright);
void SwapRows(float* s, float* d);
//-------------------------------
void QuickSortA(int sortcol, int xa, int xe)
{
qusortA(sortcol, xa, xe-xa);
}
//---------------------------------
void qusortA(int sortcol, int left, int right)
{
int l = left, r = right, m = (l+r)/2;
float x=fArray[m];

do {<font color=red>
//1 --------------------------
<font color=darkgreen> while ( fArray[l] < x ) l++;
while ( x < fArray[r] ) r--;</font>
//2 --------------------------
// while ( fArray[l] < fArray[m] )l++;
// while ( fArray[m] < fArray[r] )r--;
//3 --------------------------
// while ( IsLessThen(1,l,m)) l++;
// while ( IsLessThen(1,m,r)) r--;</font>
if(l <= r ) {
if ( l < r ) SwapRowsA( &fArray[l], &fArray[r] ); l++; r--;}
} while(l <= r);

if (left < r ) qusortA(sortcol, left, r );
if (l < right) qusortA(sortcol, l, right);
}
//----------------------------------------

bool IsLessThen(int sortcol, int vleft, int vright)
{
return (fArray[vleft] < fArray[vright]);
}
//-----------------------------------------

void SwapRowsA(float* v1, float* v2)
{
float ftemp = *v1;
*v1 = *v2;
*v2 = ftemp;
}</pre>
Leider vermag ich nicht zu erkennen, warum es die Alternativen 2 und 3 nicht tun, sondern identisch falsche Sortierergebnisse liefern.

Ausgangs-Datenreihe:<br>
| 30 | 82 | 90 | 56 | 17 | 95 | 15 | 48 | 26 | 4 | 58 | 71 |<br>
Sortiert mit (1)<br>
| 4 | 15 | 17 | 26 | 30 | 48 | 56 | 58 | 71 | 82 | 90 | 95 |<br>
Sortiert mit (2) und<br>
Sortiert mit (3)<br>
| 4 | 15 | 17 | 26 | 30 | 56 | 58 |<font color=red> 48</font> | 71 | 82 | 90 | 95 |</br>
Für Hinweise, wie ich die Alternative zum ordnungsgemäßen Laufen bringen kann, wäre ich dankbar, da ich nun hier wohl "betriebsblind" bei der Ursachenforschung geworden bind.

Gruß

[Christian Marquardt]

Beitrag 2?

[Uwe Richtsteig]

Trotz der doppelten Fragezeichen, kann ich leider denn Bezug der Frage nicht recht erkennen.

Sollte er darin bestehen, dass zwei Beitrage von mir zum Thema hintereinander geschaltet wurden?

In diesem Fall liegt es daran, das Beitrag 1 die Ausgangssituation meines Problemes war und Beitrag 2 nun die Fragestellung nach der weiteren Bearbeitung des Problems: warum Alternativen 2 und 3 gegenüber Alternative 1 zu einer falschen Sortierreihe führt.

Guß,
Uw

[Uwe Richtsteig]

Hallo, Christian!

Es war wohl heute morgen etwas zu früh für mich, denn darauf gekommen, dass Du möglicherweise aus den Beitrag 2 in dieser Themenkette verweisen wolltes, bin ich nicht.

Doch m.E. kann jedoch Deine Antwort, die Du im Beitrag 2 gegeben hast, nicht erklären, warum die Alternativen 2 und 3 nur bereichsweise funktioniert, zumal mit der Integer-Variblen <b>m</b> eine gleichwertige Speicherplatz zu Deinem <b>x</b> vorgesehen ist.

Schrittweises Ausführen der Alternativen zeigen identische Beobachtungswerte bis zum zweiten Austausch. Warum an dieser Stelle dann jedoch bei den Fällen 2 und 3 im Gegensatz zur Alternativen 1 die Ausführung von <b>l++</b> einmal weniger erfolgt, dahinter bin ich noch nict gekommen.

Gruß,
Uw