Quicksort Programm hängt sich auf

[Neamalk]

Hallo Leute,
im Informatikunterricht haben wir vor nicht allzu langer mit Java begonnen und nun wurde mir Aufgabe gestellt, ein Programm zu entwerfen, welches die Effizienz von Sortieralgorithmen miteinander vergleicht. Dazu muss ich unter anderem eine Klasse für Quicksort schreiben, welche ein zufälliges Integer Array ordnet. In einem Formular wird dabei die Länge des Array, sowie der kleinste und größte Wert eingegeben. Die Methode wird mit einem Buttonclick aufgerufen. Nun hängt sich jedoch das Programm auf, wenn man auf den Button drückt, obwohl keine Fehlermeldungen angezeigt werden.
Hier ist der Quelltext für die Klasse:

public class Quick extends Oberflaeche
{
  public Quick()
  {
    super("");   
  }

  public static int[] Quicksort(int lowerbound, int upperbound, int[] zusortieren)
  {
    int i = lowerbound;
    int j = upperbound;
    //upper and lowerbound Indizes für Teillisten
   
    int pivot = zusortieren[i + (j - i ) / 2];
    //Pivotelement wird in der Mitte von upper und lowerbound festgelegt
    while (i <= j)
    {
      while (zusortieren[i] < pivot)      //von links überprüft, welche Elemente > als Pivot sind
        i++;
       
      while (zusortieren[j] > pivot)      //von rechts überprüft, welche Elemente kleiner als Pivot sind
        j--;
     
      if (i < j)                         
      /*
      *wenn ein Element rechts und links gefunden wurden, werden sie getauscht
      *Ergebnis: Elemente links von Pivot kleiner als Pivot, rechts größer
      */
      {
        int temp = zusortieren[i];
        zusortieren[i] = zusortieren[j];
        zusortieren[j] = temp;
      }
    }
   
    //Array wird in zwei Teile zerlegt, eins links vom Pivot, eins rechts
    //Teilarrays nach selbem Prinzip geordnet
    if (lowerbound < j)                     
      Quicksort(lowerbound, j, zusortieren);
   
     
    if (i < upperbound)
      Quicksort(i, upperbound, zusortieren);

    //geordnetes Array wird zurückgegeben
    return zusortieren;
  }
}

und so wird die Methode innerhalb der Buttonprozedur aufgerufen (A ist vom Typ int[]):

A = Quick.Quicksort(0, A.length - 1, A);

Hätte irgendjemand vielleicht eine Idee, wieso das Programm nicht funktioniert?
Vielen Dank schon einmal im Voraus

 

[Blender3D]

Habe Dir quicksort geschrieben der funktioniert.

public class start {
    public static void main(String[] args) {
        int[] data = { 3, 5, 3, 7 };
        quicksort(data);
        for (int i : data)
            System.out.println(i);
    }

    public static void quicksort(int[] data) {
        if (data == null || data.length == 1)
            return;
        quicksort(0, data.length - 1, data);
    }

    private static void quicksort(int left, int right, int[] data) {
        if (left < right) {
            int pos = split(left, right, data);
            quicksort(left, pos, data);
            quicksort(pos + 1, right, data);
        }
    }

    private static int split(int left, int right, int[] data) {
        int i = left;
        int j = right - 1;
        int pivot = data[right];
        do {
            // find from left element bigger than pivot
            while (data[i] < pivot && i < right - 1)
                i++;
            // find from right element smaller or equal than pivot
            while (data[j] >= pivot && j > left)
                j--;
            if (i < j)
                swap(i, j, data);

        } while (i < j); // till i passes j
        if (data[i] > pivot)
            swap(i, right, data);
        return i; // return position of pivot
    }

    private static void swap(int i, int j, int[] data) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

}

 

[Meniskusschaden]

@Neamalk: Dein Algorithmus hat noch zwei Probleme. Du näherst dich von links und rechts dem Pivotelement an, so dass zum Schluß i==j gelten müsste. In dem Fall brichst du die Schleife aber nicht ab, so dass es endlos weiter läuft.

Das zweite Problem ist, dass du die beiden zu sortierenden Teilarrays so bemisst, dass das Pivot-Element enthalten ist. Das ist unnötig, weil es sich bereits an der korrekten Position befindet und führt letztendlich dazu, dass das Programm nicht terminiert, sondern einen Stapelüberlauf erzeugt.

 

[Xyz1]

ein Programm zu entwerfen, welches die Effizienz von Sortieralgorithmen miteinander vergleicht.

Falsche Herangehensweise....
Effizienzen ermittelt man nicht ,in dem man sie misst.
Effizienzen ermittelt man durch Ableitungen und Folgerungen.

Das bedeutet, du musst dem Lehrer sagen, dass das blöde ist, die Geschwindigkeit von Sortieralgorithmen nach Implementierung anhand Beispielen zeitlich messen zu wollen.

 

[Xyz1]

if (lowerbound < j)

if (i < upperbound)

schreibe zB das soherum auf:

if (j < lowerbuound)

if (j > upperbound)

dann ist das leichter zu lesen - und etwaige Zeichendreher fallen sofort auf

public static int[] Quicksort(int lowerbound, int upperbound, int[] zusortieren)

teile das wie es @Blender3D gemacht hat in mehrere Methoden auf

while (zusortieren[i] < pivot)

da muss glaube ich eine zusätzliche Bedingung hin - oder davor
damit Du nicht out of range bist

Quicksort(lowerbound, j, zusortieren);

Endlosrekursion möglich

 

[Neamalk]

Falsche Herangehensweise....
Effizienzen ermittelt man nicht ,in dem man sie misst.
Effizienzen ermittelt man durch Ableitungen und Folgerungen.

Das bedeutet, du musst dem Lehrer sagen, dass das blöde ist, die Geschwindigkeit von Sortieralgorithmen nach Implementierung anhand Beispielen zeitlich messen zu wollen.

Die theoretische Ableitung machen wir auch, das Programm dient nur zur Anschaulichkeit.

 

[Neamalk]

@Blender3D : Vielen Dank! Es funktioniert