Quicksort Implementierung

[fradel07]

Hallo und zwar soll ich als Hausaufgabe Quicksort implementieren und habe dazu die Methoden quicksort und die helper Methode partitioniere.



Ich habe das soweit auch programmiert, aber bekomme nun beim Testen die Fehlermeldung, dass das Array [2,1] nicht richtig sortiert wurde. Hat jemand vielleicht eine Idee, wie man das ganze verbessert und richtig macht? Wenn jemand sonst noch Fehler oder Anpassungen finden sollte, dann nur her damit 😂


Vielen Dank im Vorraus.

 

[LimDul]

Code am besten in Code-Tags hier posten, das macht es lesbarer.

Du vergleichst den Eintrag an der Stelle li bzw. re mit dem Index pivotIdx - du willst das aber mit Sicherheit mit dem Wert an der Stelle pivotIdx vergleichen.

 

[fradel07]

Okay vielen Dank erstmal, aber der Fehler, dass das Array [2,1] nicht richtig sortiert wurde bleibt leider immernoch.

private void quicksort(int[] array, int liRand, int reRand) {
        if (liRand<reRand){      // rekursionsabbruch
            
        
        int pivotIdx = liRand;
        pivotIdx = partitioniere(array, liRand, reRand, pivotIdx);
        quicksort(array, liRand, pivotIdx-1);    // "neues" linkes Array wird sortiert       // rekursiver Aufruf
        quicksort(array, pivotIdx+1, reRand);    // "neues" rechtes Array wird sortiert
       }
    return;
    }

public int partitioniere(int[] array, int links, int rechts, int pivotIdx){
    
        // Gib den neuen Index des Pivot zurueck, damit das
        // "übergeordnete" Quicksort weiss, wo es als nächstes aufteilen muss:
        int li = links;
        int re = rechts-1;
        
        
        
        while (li < re){   // während der rechte "Zeiger" größer als der linke ist
            while (array[li] <= array[pivotIdx]) {    // wenn wert an der stelle links kleiner gleich dem Pivot ist, links Zeiger um 1 nach rechts verschieben
                li++;
            }
            while (array[re] > array[pivotIdx]) {    // wenn wert an der stelle rechts größer als das Pivot ist, rechts zeiger um 1 nach links verschieben
                re--;
            }
            if(array[li]>array[re]) {           // wenn wert links größer als der wert rechts ist tauschen
                int zwisp = array[li];
                 array[li] = array[re];
                 array[re] = zwisp;
                 li++;
                 re--; 
                }
              if (li == re && array[li] < array[pivotIdx]) {   // wenn die Zeiger auf dem gleichen Wert stehen und der Wert an der Stelle links kleiner als der Wert des pivots ist links um 1
            li++;                                           // verschieben, da man dann den wert links mit dem pivot tauschen muss
              int zwisp = array[li];
            array[li] = array[pivotIdx];
            array[re] = zwisp;
            
        
            
            }       
      }
        
        
        return pivotIdx;
    }
}

 

[Barista]

Debuggen oder alternativ Zwischenergebnisse mit System.out.println ausgeben, um den Fehler einzugrenzen.