quicksort - logikproblem



  • Hey,

    ich habe mir einen quicksort geschrieben der das Pivot am Ende des Arrays hat :

    public void quicky(int anfang,int ende) {
    		int pivot = ende - 1;
    		int klei = pivot - 1;
    		int gro = anfang;
    
    		if(klei >= gro) {
    			while(klei > gro) {
    				while(gro != klei && zahlen[gro] <= zahlen[pivot]) {
    					++gro;
    				}
    
    				while(gro != klei && zahlen[klei] > zahlen[gro]) {
    					--klei;
    				}
    
    				tausche(gro,klei);
    			}
    
    			if(zahlen[pivot] < zahlen[gro]) {
    				tausche(pivot,gro);
    			} else {
    				gro = pivot;
    			}
    
    			quicky(gro + 1,ende);
    			quicky(anfang,gro);
    		}
    	}
    

    Nun will ich aber das das Pivot am Anfang ist, und habe mir gedacht das es eiegntlich nur 4 stellen gibt wo ich was ändern muss:

    public void quicky(int anfang,int ende) {
    		int pivot = anfang;  //1. Hier muss das Pivot auf den Anfang gesetzt werden
    		int klei = ende - 1; //2.Hier angleichen damit man noch im array bleibt
    		int gro = anfang + 1;  //3. Hier den (nach größeren) suchenden index einen nach rechts verschieben, da er ja sonst auf das pivot zeigen würde
    
    		if(klei >= gro) {
    			while(klei > gro) {
    				while(gro != klei && zahlen[gro] <= zahlen[pivot]) {
    					++gro;
    				}
    
    				while(gro != klei && zahlen[klei] > zahlen[gro]) {
    					--klei;
    				}
    
    				tausche(gro,klei);
    			}
    
    			if(zahlen[pivot] > zahlen[gro]) {  //hier nun noch das < in ein > , da ja das pivot nun kleiner und nicht größer seinen darf
    				tausche(pivot,gro);
    			} else {
    				gro = pivot;
    			}
    
    			quicky(gro + 1,ende);
    			quicky(anfang,gro);
    		}
    	}
    

    Fazit: Entropie pur. Wieso ist das so? In wie fern habe ich da einen eklatanten Logikfehler gemacht?

    Danke für eure Hilfe.

    PS: Ich weiß das das kein schöner c++ code ist, aber hier geht es mir um die logik und das verständnis von quicksort und weniger um schönen code 😉


Anmelden zum Antworten