J
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
