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
