Tauschen, Sortieren, Unterprogramme

Zwei Werte tauschen

In a steht 5, in b steht 8, und danach soll es umgekehrt sein. Der naheliegende Versuch a = b, dann b = a geht schief. Erinnere dich an Lektion 2: Eine Zuweisung überschreibt den alten Wert der Variablen links, und der ist danach weg.

Ohne hilf stünde nach a = b in beiden Variablen die 8, und b = a wäre wirkungslos. Der Tausch ist also immer ein Dreischritt:

hilf = a
a = b
b = hilf

Die Hilfsvariable heißt in Lösungshinweisen oft hilf, temp oder tausch; der Name ist egal, die drei Zeilen nicht. Bei einem Feld (Array) tauschst du genauso, nur mit indizierten Elementen: hilf = zahlen[i], zahlen[i] = zahlen[i + 1], zahlen[i + 1] = hilf. Genau das braucht das Sortieren.

Bubblesort

Bubblesort sortiert ein Feld aufsteigend nach einer einfachen Idee: Gehe das Feld von vorn nach hinten durch und vergleiche jedes Element mit seinem rechten Nachbarn. Steht links der größere Wert, tausche die beiden. Nach einem solchen Durchlauf ist das größte Element ganz hinten angekommen; es ist wie eine Luftblase nach oben gestiegen, daher der Name. Dann beginnt der nächste Durchlauf, der nur noch bis vor das bereits einsortierte Ende gehen muss.

FÜR durchlauf = 1 BIS n - 1
    FÜR i = 1 BIS n - durchlauf
        WENN zahlen[i] > zahlen[i + 1] DANN
            hilf = zahlen[i]
            zahlen[i] = zahlen[i + 1]
            zahlen[i + 1] = hilf
        ENDE WENN
    ENDE FÜR
ENDE FÜR

Zwei Zählschleifen ineinander. Die äußere zählt die Durchläufe: Bei n Elementen reichen n − 1, weil nach jedem Durchlauf ein weiteres Element hinten sicher steht und das letzte übrig bleibende von selbst richtig liegt. Die innere Schleife vergleicht die Nachbarpaare und läuft nur bis n − durchlauf, weil dahinter schon sortiert ist. Der Vergleich zahlen[i] > zahlen[i + 1] greift bis auf zahlen[n - durchlauf + 1] zu, im ersten Durchlauf also bis zum letzten Element; das ist der Grund, warum die innere Grenze eins kleiner sein muss als die Anzahl der noch unsortierten Elemente.

Der Schreibtischtest für zahlen = [5, 2, 4, 1] mit n = 4, das erste Element hat den Index 1. Die Spalte „Feld danach“ zeigt den Zustand nach dem jeweiligen Vergleich:

Nach Durchlauf 1 steht die 5 hinten, nach Durchlauf 2 die 4 an vorletzter Stelle, nach Durchlauf 3 ist das Feld sortiert. Die innere Schleife hat 3, 2 und 1 Durchläufe, zusammen 6 Vergleiche; allgemein sind es n · (n − 1) / 2. Das musst du nicht herleiten können, aber es erklärt, warum Bubblesort bei großen Feldern langsam ist und in Lehrbüchern und Aufgaben trotzdem verbreitet ist: Er ist kurz und lässt sich gut nachvollziehen.

Unterprogramme: Funktion und Prozedur

Die Grundmuster aus Lektion 5 tauchen in größeren Aufgaben mehrfach auf. Statt sie jedes Mal neu hinzuschreiben, lagerst du sie in ein Unterprogramm aus: ein eigenes Struktogramm mit Namen, das vom Hauptprogramm aufgerufen wird. Zwei Arten gibt es:

• Eine Funktion liefert ein Ergebnis zurück. Die letzte Anweisung ist typischerweise Rückgabe …, und der Aufruf steht dort, wo man den Wert braucht: in einer Zuweisung oder in einer Bedingung.
• Eine Prozedur tut etwas (gibt aus, verändert ein Feld), liefert aber nichts zurück. Sie wird als eigene Anweisung aufgerufen.

Der Titel des Struktogramms ist die Signatur: Name, in Klammern die Parameter mit Datentyp, und bei Funktionen nach dem Doppelpunkt der Rückgabetyp. Parameter sind die Werte, die der Aufrufer hineingibt; im Unterprogramm benutzt du sie wie Variablen.

FUNKTION istGerade(zahl: Ganzzahl): Wahrheitswert
    WENN zahl MOD 2 == 0 DANN
        RÜCKGABE wahr
    SONST
        RÜCKGABE falsch
    ENDE WENN
ENDE FUNKTION

istGerade(7) liefert falsch, istGerade(10) wahr. Kürzer wäre eine einzige Anweisung Rückgabe zahl MOD 2 == 0; beides ist richtig. Die Summe aus Lektion 5 als Funktion mit zwei Parametern:

FUNKTION summe(zahlen: Feld, n: Ganzzahl): Ganzzahl
    ergebnis = 0
    FÜR i = 1 BIS n
        ergebnis = ergebnis + zahlen[i]
    ENDE FÜR
    RÜCKGABE ergebnis
ENDE FUNKTION

Beachte den Namen ergebnis für den Akkumulator: Die Variable darf nicht so heißen wie die Funktion selbst, sonst wird es beim Lesen unklar. Und eine Prozedur, die ein Feld ausgibt:

PROZEDUR ausgabeFeld(zahlen: Feld, n: Ganzzahl)
    FÜR i = 1 BIS n
        AUSGABE zahlen[i]
    ENDE FÜR
ENDE PROZEDUR

Der Aufruf im Hauptprogramm

Für den Aufruf einer Prozedur ist ein eigener Kasten mit doppelten Seitenlinien üblich. Das Ergebnis einer Funktion wird dagegen meist in einer normalen Anweisung verwendet, also zugewiesen oder direkt in einer Bedingung geprüft:

ausgabeFeld(zahlen, n)
gesamt = summe(zahlen, n)
AUSGABE gesamt
WENN istGerade(gesamt) DANN
    AUSGABE "Summe ist gerade"
SONST
    AUSGABE "Summe ist ungerade"
ENDE WENN

Beim Aufruf stehen die Argumente in derselben Reihenfolge wie die Parameter in der Signatur: summe(zahlen, n) übergibt das Feld an zahlen und die Anzahl an n. Für zahlen = [4, 9, 2, 7] gibt das Hauptprogramm 4, 9, 2, 7 aus, dann 22, dann „Summe ist gerade“. Ob du den Funktionsaufruf mit Zuweisung als normale Anweisung oder ebenfalls im Aufrufkasten zeichnest, ist in vielen Lösungshinweisen gleichwertig; wichtig ist, dass der Rückgabewert irgendwo landet und nicht verloren geht. Wird ein Feld übergeben, bekommt das Unterprogramm das Feld selbst, keine Kopie: Änderungen an den Elementen, etwa durch ein Sortieren, wirken nach außen und sind nach dem Aufruf im Hauptprogramm sichtbar.

Übungen

Jetzt selbst testen

Vier Fragen zu Tauschen, Bubblesort und Unterprogrammen.