Quicksort



  • 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);
    	}
    }
    


  • 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);
    	}
    }
    


  • 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--;
    


  • jo danke. Habs oben schon korrigiert 🙂



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



  • 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"


Log in to reply