Quicksort von Array mit gleichen Zahlen



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


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



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


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


Log in to reply