Quicksort von Array mit gleichen Zahlen

mstrkrft_

Hallo,

ich habe einen Quicksortalgorithmus geschrieben. Allerdings ist mir aufgefallen, dass das Prinzip bei gleichen Zahlen versagt. Kann mir jemand weiterhelfen, wie ich das Programm ändern kann, damit es auch damit klappt.

Mein Code

int* quicksort(int feld[], int l){

	int i = 0;
	int j = l-1;
	int p = j/2;

	while(i<j){

		while(feld[i]<feld[p]) i++;

		while(feld[j]>feld[p]) j--;

		swap(feld,i,j);

		if(p==i) p=j;
		else if(p==j) p=i;
	}

	if(l>1){
			quicksort(feld,p);
			quicksort(feld+p+1,l-p-1);
	}

	return feld;	
}

volkard

Ist zwar gar nicht ausführlich, aber vielleicht kannst Du da Ideen abstauben.
http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf

mstrkrft_

Ah habs schon gefunden.

Ich habe lediglich den Index von i bzw j pauschal bei der Überprüfung ob p==i bzw j in- bzw dekrementiert(Zeile 15 und 16). So erreicht man, dass die "Zeiger" nicht auf Zahlen des selben Wertes hängen bleiben.

int* quicksort(int feld[], int l){

	int i = 0;
	int j = l-1;
	int p = j/2;

	while(i<j){

		while(feld[i]<feld[p]) i++;

		while(feld[j]>feld[p]) j--;

		swap(feld,i,j);

		if(p==i){p=j; i++;}
		else if(p==j){p=i; j--;}
	}

	if(l>1){
			quicksort(feld,p);
			quicksort(feld+p+1,l-p-1);
	}

	return feld;	
}

volkard

Da hatte ich Dich falsch verstanden. Unter "versagen" hatte ich nur erwartet, daß die Performance böse einbricht bei gleichen Werten.