Mal wieder Quicksort - mal wieder nicht ganz richtig sortiert

FlashMuller

Hallo Forum,
tut mir schon fast leid, dass ich ein weiteres Quicksort-thema eröffne. Ähnlich Beiträge gab es schon, allerdings kann ich die Lösung nicht transferieren.

Zur vorherigen Klärung von feldZeiger und feld_SORT_P:
feldZeiger[Nr].z ist das Sortiermerkmal (double);
Da ich die Nr von feldZeiger auf jeden Fall noch brauche, also nicht einfach den "z" Wert hin und her schieben kann, benutze ich feld_SORT_P um der Sortierungsreihenfolge einen feldZeiger zuordnen zu können. Hoffe das war einigermaßen klar

Folgenden Code habe ich:

void Hoehensortierung(int left, int right)
{
	int i = left;
	int j = right;
	int tmp;
	double pivot = feldZeiger[feld_SORT_P[(left + right) / 2]].z; 

	//Partitionieren
	while (i<=j)
	{

		while(feldZeiger[feld_SORT_P[i]].z < pivot && i<j) 
			i++; 
		while(feldZeiger[feld_SORT_P[j]].z >= pivot && j>i)
			j--;

		if(i<=j)
		{
			tmp = feld_SORT_P[i];
			feld_SORT_P[i] = feld_SORT_P[j];
			feld_SORT_P[j] = tmp;
			i++;
			j--;
		}
	};
	//Stimmt bis hierhin bei einmaligem Durchlauf
	if(left < j)
		Hoehensortierung(left, j);
	if(i < right)
		Hoehensortierung(i+1, right);
}

Das Ergebniss ist statt 1, 2, 3, 4, 5, ...
-> 4, 1, 2, 3, danach wird es total hahnebüchen.
Wäre sehr dankbar für Hilfe, irgendwo ist die Logiklücke und ich fühl mich wie der bekannte Ochs vorm Berg...
Grüße

BasicMan01

mit dem ganzen Code wäre es einfacher

while(feldZeiger[feld_SORT_P[j]].z >= pivot && j>i)

Hier scheint mir das >= falsch. > sollte reichen, da das Pivot-Elemente ja die Mitte darstellt und nur die Elemente davor / dahinter jeweils auf die richtige Seite "getauscht" werden.

Hoehensortierung(i+1, right);

auch die +1 könnte weg.
damit würde ja ein Element übersprungen und zwar das Element mit Wert i.
Die rechte Seite sollte analog zur linken Seite durchgeführt werden

FlashMuller

Danke für die schnelle Antwort. Viel mehr code gibt es da eigentlich nicht, ausser die Definitionen von feldZeiger und feld_SORT_P:

class feld 
{
	public:
		int id;
		int x;
		int y;
		double z;
		int empf[8];
		double entw;
};
feld *feldZeiger; 
...
feldZeiger = new feld[xy_gesamt];

feld_SORT_P entspricht bei seiner Initialisierung der id von FeldZeiger.

Habe deine Tips umgesetzt. Das Ergebniss hat sich dadurch verändert, ist aber immernoch nicht richtig:
1, 5, 2, 3, 4, 7, 6, 8, 9...
Grüße und Danke soweit

BasicMan01

ich bleibe bei meinen Angaben von oben
allerdings würde ich das mit dem pivot-element etwas vereinfachen.
du benotigst im Prinzip nur den Index des Pivot und ließt das direkt aus deinem
Array aus.

// an den Anfang der Funktion
    int middle = (left + right) / 2;

    while (i<=j)
    {
        while(feldZeiger[i].z < feldZeiger[middle].z)
            i++;
        while(feldZeiger[j].z > feldZeiger[middle].z)
            j--;

        // tausch
     };

    if(left < j)
        Hoehensortierung(left, j);
    if(i < right)
        Hoehensortierung(i, right);

FlashMuller

void Hoehensortierung(int left, int right)
{
	int i = left;
	int j = right;
	int middle = (left + right) / 2;
	int tmp;

	//Partitionieren
	while (i<=j)
	{

		while(feldZeiger[feld_SORT_P[i]].z < feldZeiger[feld_SORT_P[middle]].z) 
			i++; 
		while(feldZeiger[feld_SORT_P[j]].z > feldZeiger[feld_SORT_P[middle]].z)
			j--;

		if(i<=j)
		{
			tmp = feld_SORT_P[i];
			feld_SORT_P[i] = feld_SORT_P[j];
			feld_SORT_P[j] = tmp;
			i++;
			j--;
		}
	};

	if(left < j)
		Hoehensortierung(left, j);
	if(i < right)
		Hoehensortierung(i, right);
}

So funktionierts. Die Modifikation der beiden while-schleifen war der Schlüssel, wie es scheint.
Danke für deine Hilfe.
Grüße