QuickSort: Sortieren durch Zerlegen

So sieht das vollständige Zerlegen für eine Beispielliste aus. Gelb ist jeweils das Pivot. Jede Zeile zeigt eine Zerleg-Runde tiefer:

🔁 Das neue Werkzeug: Rekursion

Bei BubbleSort hast du Schleifen benutzt: wiederhole etwas mehrmals. QuickSort braucht zusätzlich Rekursion: eine Methode ruft sich selbst auf, aber jedes Mal mit einer kleineren Aufgabe. Damit das nicht ewig weitergeht, gibt es eine Abbruchregel:

Du erweiterst deine bestehende Klasse Main. Nichts löschen! BubbleSort und SelectionSort bleiben drin, du brauchst sie später noch für den Vergleich.

    /**
     * QuickSort: Startdienst.
     * Setzt die Zaehler zurueck und sortiert das ganze Feld
     * von Index 0 bis Index anzahl - 1.
     */
    public void quickSort()
    {
        vergleiche = 0;
        tausche = 0;
        zeichne("QuickSort", -1, -1, -1, -1,
                "Zerlegen mit Pivot. Los geht es!");
        uhr.warte(900);

        sortiereBereich(0, anzahl - 1);

        zeichne("QuickSort fertig", -1, -1, -1, 0,
                "Fertig! Rufe neueZahlen() und bubbleSort() auf und vergleiche.");
    }

    /**
     * AUFGABE: Sortiert den Bereich von anfang bis ende mit QuickSort.
     * Diese Methode ruft sich selbst auf (Rekursion).
     */
    private void sortiereBereich(int anfang, int ende)
    {
        int pivot;
        int links;
        int rechts;

        // TODO 1: Pivot und Zeiger setzen
        //   pivot  = die Zahl an der Stelle anfang
        //   links  = anfang
        //   rechts = ende

        // TODO 2: Zerlegen, solange links <= rechts ist:
        //   a) links wandert nach rechts (links = links + 1),
        //      solange zahlen[links] kleiner als pivot ist
        //   b) rechts wandert nach links (rechts = rechts - 1),
        //      solange zahlen[rechts] groesser als pivot ist
        //   c) wenn links <= rechts:
        //        wenn links < rechts: tausche(links, rechts)
        //        danach: links um 1 erhoehen, rechts um 1 verringern

        // TODO 3: Rekursion fuer die beiden Teilbereiche:
        //   wenn anfang < rechts: sortiereBereich(anfang, rechts)
        //   wenn links  < ende:   sortiereBereich(links, ende)

        // Tipp fuer die Anzeige zwischendurch:
        //   zeichne("QuickSort", links, rechts, anfang, -1, "...");
        //   uhr.warte(700);
        // Der dritte Wert (anfang) faerbt das Pivot gelb,
        // links und rechts werden rot markiert.
    }