SelectionSort: Immer das Kleinste zuerst

In der Vorlage ist bubbleSort() komplett fertig. Nutze es als Spickzettel: Dort siehst du, wie Schleifen, Vergleiche, tausche(...), zeichne(...) und uhr.warte(...) zusammenspielen. Deine Baustelle ist nur die Methode selectionSort() mit ihren vier TODOs.

import sum.kern.*;
import sum.werkzeuge.*;

/**
 * Vereinfachte Sortier-Visualisierung fuer BlueJ und die SuM-Bibliothek.
 * BubbleSort ist fertig vorgegeben.
 * SelectionSort ist die Schueleraufgabe.
 */
public class Main
{
    // Bezugsobjekte
    Bildschirm derBildschirm;
    Buntstift stift;
    Uhr uhr;
    Rechner rechner;

    // Daten
    int[] zahlen;
    int anzahl;

    // Darstellung
    int links;
    int basis;
    int balkenBreite;
    int luecke;
    int faktor;

    // Zaehler
    int vergleiche;
    int tausche;

    /**
     * Konstruktor: Erzeugt Fenster und Startzahlen.
     */
    public Main()
    {
        derBildschirm = new Bildschirm(720, 500, true);
        stift = new Buntstift();
        uhr = new Uhr();
        rechner = new Rechner();

        anzahl = 8;
        links = 60;
        basis = 400;
        balkenBreite = 50;
        luecke = 18;
        faktor = 4;

        zahlen = new int[anzahl];
        neueZahlen();
    }

    /**
     * Erzeugt eine neue unsortierte Zahlenliste.
     */
    public void neueZahlen()
    {
        int i;
        for(i = 0; i < anzahl; i++)
        {
            zahlen[i] = rechner.ganzeZufallsZahl(15, 80);
        }
        vergleiche = 0;
        tausche = 0;
        zeichne("Neue Zahlen", -1, -1, -1, -1,
                "Rufe jetzt bubbleSort() oder deine Methode selectionSort() auf.");
    }

    /**
     * BubbleSort ist als Beispiel komplett vorgegeben.
     * Idee: Nach jeder Runde ist rechts eine weitere Zahl sicher sortiert.
     */
    public void bubbleSort()
    {
        int runde;
        int i;

        vergleiche = 0;
        tausche = 0;
        zeichne("BubbleSort", -1, -1, -1, anzahl,
                "Benachbarte Zahlen werden verglichen.");
        uhr.warte(900);

        for(runde = 0; runde < anzahl - 1; runde++)
        {
            for(i = 0; i < anzahl - 1 - runde; i++)
            {
                vergleiche++;
                zeichne("BubbleSort", i, i + 1, -1, anzahl - runde,
                        "Vergleich: Stehen diese Nachbarn falsch herum?");
                uhr.warte(700);

                if(zahlen[i] > zahlen[i + 1])
                {
                    tausche(i, i + 1);
                    tausche++;
                    zeichne("BubbleSort", i, i + 1, -1, anzahl - runde,
                            "Tausch: Die groessere Zahl wandert nach rechts.");
                    uhr.warte(700);
                }
            }
            zeichne("BubbleSort", -1, -1, -1, anzahl - runde - 1,
                    "Runde fertig: Rechts ist ein weiterer Balken sortiert.");
            uhr.warte(500);
        }
        zeichne("BubbleSort fertig", -1, -1, -1, 0,
                "Fertig. Vergleiche die Anzahl der Vergleiche und Tausche.");
    }

    /**
     * AUFGABE: Programmiere SelectionSort.
     *
     * Idee:
     * 1. i zeigt auf die erste freie Stelle links.
     * 2. kleinsteStelle merkt sich die Stelle mit der kleinsten Zahl.
     * 3. j durchsucht den unsortierten Bereich rechts von i.
     * 4. Am Ende wird die kleinste gefundene Zahl nach i getauscht.
     */
    public void selectionSort()
    {
        int i;
        int j;
        int kleinsteStelle;

        vergleiche = 0;
        tausche = 0;
        zeichne("SelectionSort: noch unvollstaendig", -1, -1, -1, -1,
                "Ersetze diese Methode mithilfe der Lernstrecke.");
        uhr.warte(1200);

        // TODO 1: aeussere Schleife fuer die Runden:
        //   for(i = 0; i < anzahl - 1; i++)

        // TODO 2: Am Anfang jeder Runde den Merkzettel setzen:
        //   kleinsteStelle = i;

        // TODO 3: innere Schleife, die den Rest durchsucht:
        //   for(j = i + 1; j < anzahl; j++)
        //   Vergleiche zahlen[j] mit zahlen[kleinsteStelle].
        //   Wenn zahlen[j] kleiner ist: kleinsteStelle = j;

        // TODO 4: Nach der inneren Schleife:
        //   Wenn kleinsteStelle nicht i ist: tausche(i, kleinsteStelle);

        // Tipp fuer die Anzeige zwischendurch:
        //   zeichne("SelectionSort", j, -1, kleinsteStelle, -1, "...");
        //   uhr.warte(700);
        // Damit wird j rot und kleinsteStelle gelb markiert.
    }

    /**
     * Tauscht zwei Werte im Feld zahlen.
     */
    private void tausche(int a, int b)
    {
        int hilfe;
        hilfe = zahlen[a];
        zahlen[a] = zahlen[b];
        zahlen[b] = hilfe;
    }

    /**
     * Zeichnet das komplette Bild neu.
     * vergleichA und vergleichB werden rot markiert.
     * minimum wird gelb markiert.
     * sortiertAb bedeutet: ab diesem Index ist rechts sortiert (gruen).
     */
    private void zeichne(String titel, int vergleichA, int vergleichB,
                         int minimum, int sortiertAb, String meldung)
    {
        int i;
        int x;
        int y;
        int hoehe;

        // Hintergrund
        stift.setzeFuellmuster(Muster.GEFUELLT);
        setzeFarbe(245, 247, 250);
        stift.bewegeBis(0, 0);
        stift.zeichneRechteck(720, 500);

        // Kopf
        setzeFarbe(35, 50, 75);
        stift.bewegeBis(0, 0);
        stift.zeichneRechteck(720, 90);

        stift.setzeFarbe(Farbe.rgb(255, 255, 255));
        stift.setzeSchriftgroesse(24);
        stift.bewegeBis(30, 28);
        stift.schreibeText(titel);

        stift.setzeSchriftgroesse(14);
        stift.bewegeBis(360, 25);
        stift.schreibeText("Vergleiche: ");
        stift.schreibeZahl(vergleiche);
        stift.bewegeBis(360, 50);
        stift.schreibeText("Tausche: ");
        stift.schreibeZahl(tausche);

        // Meldung
        stift.setzeFarbe(Farbe.rgb(40, 40, 40));
        stift.setzeSchriftgroesse(15);
        stift.bewegeBis(30, 118);
        stift.schreibeText(meldung);

        // Grundlinie
        stift.setzeFuellmuster(Muster.DURCHSICHTIG);
        stift.setzeFarbe(Farbe.rgb(0, 0, 0));
        stift.setzeLinienbreite(2);
        stift.bewegeBis(45, basis);
        stift.runter();
        stift.bewegeBis(665, basis);
        stift.hoch();
        stift.setzeLinienbreite(1);

        // Balken
        for(i = 0; i < anzahl; i++)
        {
            x = links + i * (balkenBreite + luecke);
            hoehe = zahlen[i] * faktor;
            y = basis - hoehe;

            if(i == vergleichA || i == vergleichB)
            {
                setzeFarbe(230, 80, 70);      // rot: Vergleich
            }
            else if(i == minimum)
            {
                setzeFarbe(245, 200, 60);     // gelb: gemerktes Minimum
            }
            else if(sortiertAb >= 0 && i >= sortiertAb)
            {
                setzeFarbe(100, 180, 110);    // gruen: sortierter Bereich rechts
            }
            else
            {
                setzeFarbe(80, 140, 220);     // blau: normal
            }

            stift.setzeFuellmuster(Muster.GEFUELLT);
            stift.bewegeBis(x, y);
            stift.zeichneRechteck(balkenBreite, hoehe);

            stift.setzeFuellmuster(Muster.DURCHSICHTIG);
            stift.setzeFarbe(Farbe.rgb(0, 0, 0));
            stift.bewegeBis(x, y);
            stift.zeichneRechteck(balkenBreite, hoehe);

            stift.setzeSchriftgroesse(13);
            stift.bewegeBis(x + 10, y - 22);
            stift.schreibeZahl(zahlen[i]);

            stift.setzeFarbe(Farbe.rgb(90, 90, 90));
            stift.setzeSchriftgroesse(12);
            stift.bewegeBis(x + 18, basis + 15);
            stift.schreibeZahl(i);
        }

        derBildschirm.zeichneDich();
    }

    /**
     * Kleine Hilfsmethode, damit Farben fuer Schueler lesbarer bleiben.
     */
    private void setzeFarbe(int r, int g, int b)
    {
        stift.setzeFarbe(Farbe.rgb(r, g, b));
    }
}