Quicksort

blurry333

Hallo,

in meiner sortiere funktion scheint noch irgendwo ein Fehler drin zu sein. Ich find den grad net

int sortiere(int* arr, int left , int pivot)
{
	int right = pivot;
	while(left<right)
	{
		while(arr[++left] < arr[pivot] && left < right );
		while(arr[--right] > arr[pivot] && right > left );
		swap(arr[left],arr[right]);
	}
	swap(arr[left],arr[pivot]);
	pivot = left;
	return pivot;
}

void quicksort(int* arr, int left , int right)
{
	if(left<right)
	{
		int pivot = sortiere(arr,left,right);
		quicksort(arr,left,pivot-1);
		quicksort(arr,pivot+1,right);
	}
}

blurry333

So ist er richtig(pseudo Code wikipedia).

int sortiere(int* arr, int left , int right)
{
	int i = left;
	int j = right-1;
	int pivot = arr[right];

	do
	{
		while(arr[i] <= pivot && i < right ) i++;
		while(arr[j] >= pivot && j > left ) j--;
		if(i<j)
			swap(arr[i],arr[j]);
	}
	while(i<j);

	if(arr[i] > pivot)
		swap(arr[i],arr[right]);
	return i;
}

void quicksort(int* arr, int left , int right)
{
	if(left<right)
	{
		int pivot = sortiere(arr,left,right);
		quicksort(arr,left,pivot-1);
		quicksort(arr,pivot+1,right);
	}
}

Skym0sh0

Nein ist nicht der Code von Wikipedia.

while(arr[j] >= pivot && j > left ) j++;

Die Schleife ist falsch.

=>

while(arr[j] >= pivot && j > left ) j--;

blurry333

jo danke. Habs oben schon korrigiert

blurry333

Es wird ja eine do while schleife benutzt. Ist das nicht unsinnig ? Kann mir einer ein Beispiel nennen wo es einen Unterschied macht.

volkard

blurry333 schrieb:

Es wird ja eine do while schleife benutzt. Ist das nicht unsinnig ? Kann mir einer ein Beispiel nennen wo es einen Unterschied macht.

google "kopfgesteuert"