1. Worum geht es?
Du siehst eine Liste von Zahlen als Balken. Ein Sortierverfahren bringt die Balken in die richtige Reihenfolge: links klein, rechts groß.
Heute sicher können
Du erklärst, warum BubbleSort immer benachbarte Zahlen vergleicht und warum rechts nach jeder Runde ein sortierter Bereich wächst.
Heute selbst programmieren
Du programmierst SelectionSort: Suche im unsortierten Bereich das kleinste Element und tausche es nach links.
2. Zwei Sortierideen vergleichen
| BubbleSort | SelectionSort |
|---|---|
| Vergleicht immer zwei Nachbarn. Ist die linke Zahl größer, werden beide vertauscht. | Sucht zuerst das kleinste Element im noch unsortierten Bereich. |
| Nach einer Runde ist die größte Zahl rechts angekommen. | Nach einer Runde steht links ein weiteres Element fest an der richtigen Stelle. |
| Viele kleine Tausche. | Meist wenige Tausche, aber weiterhin viele Vergleiche. |
Laufzeit-Idee: Wenn die Liste doppelt so lang wird, braucht ein einfaches Sortierverfahren nicht nur doppelt so viel Arbeit. Weil viele Zahlen mit vielen anderen verglichen werden, wächst die Arbeit ungefähr quadratisch.
3. Mini-Simulator im Browser
Nutze den Simulator zuerst, bevor du in BlueJ programmierst. Achte darauf, welche Stelle gerade verglichen wird und wo der sortierte Bereich entsteht.
Bereit.
4. Lückentext: SelectionSort verstehen
Fülle die Begriffe ein und prüfe danach selbst.
5. BlueJ-Anleitung
BlueJ öffnen. Wähle Project → New Project und gib dem Projekt z. B. den Namen
Sortieren.Neue Klasse erstellen. Klicke auf New Class, wähle Class und nenne sie genau
Main.Code einfügen. Öffne die Klasse
Main, lösche den alten Inhalt und füge die Vorlage aus Abschnitt 7 ein.Übersetzen. Klicke auf Compile. Falls Fehler angezeigt werden, kontrolliere Klammern, Semikolons und die Klassennamen.
Starten. Rechtsklick auf die Klasse
Main → new Main(). Der Konstruktor erzeugt das Fenster und neue Zahlen.Dienste aufrufen. Rechtsklick auf das erzeugte rote Objekt unten →
bubbleSort(), neueZahlen() oder später selectionSort().6. Programmierauftrag: SelectionSort
BubbleSort ist bereits fertig. Du benutzt BubbleSort als Lesebeispiel: Dort siehst du Schleifen, Vergleich, Tausch, Zeichnen und Warten.
Algorithmus in Worten: Für jede Position
i von links nach rechts: Merke dir zunächst i als kleinste Stelle. Suche mit j rechts davon weiter. Findest du eine kleinere Zahl, aktualisiere kleinsteStelle. Nach der Suche tauschst du i mit kleinsteStelle.
Pseudocode
for i von 0 bis anzahl - 2:
kleinsteStelle = i
for j von i + 1 bis anzahl - 1:
wenn zahlen[j] kleiner als zahlen[kleinsteStelle]:
kleinsteStelle = j
wenn kleinsteStelle nicht i ist:
tausche(i, kleinsteStelle)7. Codevorlage für BlueJ
Kopiere diese Vorlage in die Klasse Main. Sie ist absichtlich klein gehalten: Nur BubbleSort ist fertig, SelectionSort enthält Arbeitsstellen.
import sum.kern.*;
import sum.werkzeuge.*;
/**
* Vereinfachte Sortier-Visualisierung fuer BlueJ und die SuM-Bibliothek.
*
* Ablauf in BlueJ:
* 1. Projekt oeffnen.
* 2. Klasse Main erstellen.
* 3. Diesen Code einfuegen und uebersetzen.
* 4. Rechtsklick auf Main -> new Main().
* 5. Danach am Objekt die Dienste neueZahlen(), bubbleSort() und selectionSort() aufrufen.
*
* 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:
// for(i = 0; i < anzahl - 1; i++)
// TODO 2: Am Anfang jeder Runde:
// kleinsteStelle = i;
// TODO 3: innere Schleife:
// for(j = i + 1; j < anzahl; j++)
// Vergleiche zahlen[j] mit zahlen[kleinsteStelle].
// Wenn zahlen[j] kleiner ist, setze kleinsteStelle = j.
// TODO 4: Nach der inneren Schleife:
// Wenn kleinsteStelle nicht i ist, tausche i und kleinsteStelle.
// Tipp: Nutze zwischendurch:
// zeichne("SelectionSort", j, -1, kleinsteStelle, i, "...");
// uhr.warte(700);
}
/**
* 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.
* Bei SelectionSort kann sortiertAb auch als "bis i links sortiert" gelesen werden,
* wenn du es entsprechend im Aufruf benutzt.
*/
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));
}
}
Lehrkraft: mögliche Lösung anzeigen
Diese Lösung ist auch als eigene Datei im Paket enthalten.
import sum.kern.*;
import sum.werkzeuge.*;
/**
* Vereinfachte Sortier-Visualisierung fuer BlueJ und die SuM-Bibliothek.
*
* Ablauf in BlueJ:
* 1. Projekt oeffnen.
* 2. Klasse Main erstellen.
* 3. Diesen Code einfuegen und uebersetzen.
* 4. Rechtsklick auf Main -> new Main().
* 5. Danach am Objekt die Dienste neueZahlen(), bubbleSort() und selectionSort() aufrufen.
*
* 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", -1, -1, -1, -1,
"Wir suchen immer das kleinste Element im unsortierten Bereich.");
uhr.warte(900);
for(i = 0; i < anzahl - 1; i++)
{
kleinsteStelle = i;
zeichne("SelectionSort", i, -1, kleinsteStelle, -1,
"Runde startet: Stelle i soll als naechstes gefuellt werden.");
uhr.warte(700);
for(j = i + 1; j < anzahl; j++)
{
vergleiche++;
zeichne("SelectionSort", j, kleinsteStelle, kleinsteStelle, -1,
"Vergleich: Ist j kleiner als das bisherige Minimum?");
uhr.warte(700);
if(zahlen[j] < zahlen[kleinsteStelle])
{
kleinsteStelle = j;
zeichne("SelectionSort", j, -1, kleinsteStelle, -1,
"Neues Minimum gefunden.");
uhr.warte(700);
}
}
if(kleinsteStelle != i)
{
tausche(i, kleinsteStelle);
tausche++;
zeichne("SelectionSort", i, kleinsteStelle, -1, -1,
"Tausch: Das Minimum kommt nach links.");
uhr.warte(700);
}
zeichne("SelectionSort", -1, -1, -1, -1,
"Stelle " + i + " ist jetzt fertig sortiert.");
uhr.warte(500);
}
zeichne("SelectionSort fertig", -1, -1, -1, 0,
"Fertig: SelectionSort hat oft wenige Tausche, aber viele Vergleiche.");
}
/**
* 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.
* Bei SelectionSort kann sortiertAb auch als "bis i links sortiert" gelesen werden,
* wenn du es entsprechend im Aufruf benutzt.
*/
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));
}
}
8. Hilfen und Differenzierung
Hilfe 1: Welche Schleife?
Die äußere Schleife bestimmt, welche linke Stelle als nächstes fertig wird: i.
Hilfe 2: Was merkt man sich?
kleinsteStelle speichert nicht die kleinste Zahl, sondern die Stelle im Feld.
Hilfe 3: Was vergleicht man?
Vergleiche zahlen[j] mit zahlen[kleinsteStelle].
Zusatzauftrag
Ergänze eine Meldung im Bild, die nach jeder Runde sagt: „Stelle i ist fertig sortiert.“
Typische Fehler:
kleinsteStelle = zahlen[j] ist falsch. Du brauchst die Stelle, nicht den Wert. Richtig ist: kleinsteStelle = j.