Reihungen — Suchen und Sortieren: Typische Fehler – Informatik Grundkurs

Hier sind die 12 häufigsten Fehler in Klausuren zu Reihungen, Suchen und Sortieren. Lies sie durch — wer einen Fehler kennt, macht ihn seltener. Die meisten passieren an den Grenzen einer Schleife.

Die 12 häufigsten Fehler

1Schleife läuft einen Platz zu weit

i <= a.length statt i < a.length

So wird oft programmiert: Zum Aufsummieren von int[] a = new int[8];:

for (int i = 0; i <= a.length; i++) {
    summe = summe + a[i];   // i = 8: Abbruch
}

Richtig ist: Letzter gültiger Index ist a.length − 1 = 7. Beim Zugriff auf a[8] bricht das Programm mit ArrayIndexOutOfBoundsException ab.

for (int i = 0; i < a.length; i++) {
    summe = summe + a[i];
}

Zählschleife über eine Reihung: Start bei 0, Bedingung i < a.length.

2Nachbarvergleich bis zum Ende

a[j + 1] mit j < n

So wird oft programmiert: Im Bubblesort-Durchlauf:

for (int j = 0; j < a.length; j++) {
    if (a[j] > a[j + 1]) { ... }
}

Richtig ist: Beim letzten j gibt es keinen rechten Nachbarn. Der Zählbereich muss um eins kürzer sein, im Durchlauf d sogar um d:

for (int j = 0; j < a.length - d; j++) {
    if (a[j] > a[j + 1]) { ... }
}

Wer a[i + 1] oder a[i − 1] liest, verschiebt eine Grenze der Schleife.

3Maximum mit 0 begonnen

max = 0 bei negativen Werten

So wird oft programmiert: Tiefstwerte einer Gefriertruhe {−3, −7, −1, −5}: int max = 0; — Ergebnis 0.

Richtig ist: Die 0 kommt in der Reihung gar nicht vor. Mit dem ersten Element beginnen: int max = t[0]; und ab Index 1 vergleichen → Ergebnis −1.

Maximum und Minimum starten mit dem ersten Element, nie mit einer „ausgedachten“ Zahl.

4Mittelwert ganzzahlig gerechnet

summe / n mit zwei int

So wird oft programmiert: Werte {5, 4, 4, 4}: int schnitt = summe / a.length; liefert 17 / 4 = 4.

Richtig ist: Bei zwei ganzen Zahlen fällt der Rest weg. Richtig: double schnitt = (double) summe / a.length; → 4,25.

Vor dem Teilen prüfen: Sind beide Operanden ganzzahlig? Dann ist auch das Ergebnis ganzzahlig.

5Zeile und Spalte vertauscht

m[spalte][zeile], m.length als Spaltenzahl

So wird oft programmiert: Bei int[][] m = new int[3][5]; läuft die innere Schleife bis m.length und greift auf m[z][s] zu.

Richtig ist: m.length = 3 sind die Zeilen, m[0].length = 5 die Spalten. Innere Schleife: for (int s = 0; s < m[z].length; s++); sonst werden Spalten 3 und 4 nie besucht.

Erst Zeile, dann Spalte: m[zeile][spalte]. Zeilenzahl m.length, Spaltenzahl m[zeile].length.

6Lineare Suche gibt zu früh auf

return −1 im else

So wird oft programmiert: Suche nach 6 in {8, 3, 6}:

for (int i = 0; i < a.length; i++) {
    if (a[i] == x) return i;
    else return -1;   // schon nach a[0] Schluss
}

Richtig ist: Die Methode endet nach dem ersten Element mit −1, obwohl 6 an Index 2 steht. „Nicht gefunden“ steht erst nach der Schleife fest:

for (int i = 0; i < a.length; i++) {
    if (a[i] == x) return i;
}
return -1;

Ein negatives Ergebnis gilt erst, wenn alle Elemente geprüft sind.

7Binäre Suche auf unsortierten Daten

Voraussetzung vergessen

So wird oft programmiert: Suche nach 9 in {9, 2, 7, 4, 5}: mitte = 2 (7 < 9) → rechts weiter, mitte = 3, dann 4 → Ergebnis −1.

Richtig ist: Die 9 steht an Index 0, aber die Suche verwirft die linke Hälfte, weil sie annimmt, dort stünden nur kleinere Werte. Erst sortieren, sonst linear suchen.

Binäre Suche nur auf sortierten Reihungen — sie meldet sonst keinen Fehler, sondern ein falsches Ergebnis.

8Suchbereich wird nicht kleiner

links = mitte statt mitte + 1

So wird oft programmiert: Suche nach 3 in {1, 3}: links = 0, rechts = 1, mitte = 0, a[0] = 1 < 3 → links = mitte = 0 — derselbe Bereich wie vorher.

Richtig ist: Die Schleife läuft endlos. Das angesehene Element ist erledigt und muss aus dem Bereich: links = mitte + 1 bzw. rechts = mitte − 1. Dann: mitte = 1 → gefunden.

Jeder Schritt der binären Suche muss den Bereich um mindestens ein Element verkleinern.

9Tauschen ohne Hilfsvariable

zwei Zuweisungen hintereinander

So wird oft programmiert: Aus a[i] = 4, a[j] = 9 wird mit a[i] = a[j]; a[j] = a[i]; zweimal die 9.

Richtig ist: Der alte Wert von a[i] ist nach der ersten Zeile verloren. Mit Hilfsvariable: int h = a[i]; a[i] = a[j]; a[j] = h; → 9 und 4.

Dreieckstausch: erst sichern, dann überschreiben, dann zurückschreiben.

10Minimum als Wert statt als Index

Selectionsort merkt sich minWert

So wird oft programmiert: Bei {5, 2, 8} merkt sich die Minimumsuche nur minWert = 2 und schreibt a[0] = minWert; → {2, 2, 8}.

Richtig ist: Die 5 ist verloren, weil niemand weiß, wo die 2 stand. Den Index merken (min = j) und dann a[0] mit a[min] tauschen → {2, 5, 8}.

Wer tauschen will, braucht die Position — Selectionsort merkt sich den Index des Minimums.

11Schlüssel beim Einfügen überschrieben

Insertionsort ohne key

So wird oft programmiert: Bei {4, 1} wird zuerst a[1] = a[0] verschoben und danach a[i] eingesetzt → {4, 4}.

Richtig ist: Das Verschieben überschreibt genau den Platz des einzufügenden Elements. Vorher sichern: int key = a[i];, schieben, dann a[j + 1] = key; → {1, 4}.

Insertionsort: erst den Schlüssel sichern, dann Platz schaffen.

12Vergleiche und Wachstum falsch eingeschätzt

\(n^2\) statt \(\frac{n(n-1)}{2}\), „doppelt so viele Daten, doppelte Zeit“

So wird oft programmiert: Für \(n = 10\) werden 100 Vergleiche angegeben; für 2000 statt 1000 Werte wird die doppelte Sortierzeit erwartet.

Richtig ist: Selectionsort vergleicht \(9+8+\dots+1 = 45\)-mal. Von 1000 auf 2000 Werte steigt die Zahl von 499 500 auf 1 999 000 — etwa das Vierfache. Die binäre Suche braucht dagegen nur einen Schritt mehr (10 → 11).

Quadratisch: \(2n\) → etwa \(4\)-fach. Linear: doppelt. Logarithmisch: \(+1\) Schritt.

Typische Fehler — was oft schiefgeht