Daten in Reihungen
Eine Reihung fasst eine feste Anzahl gleichartiger Werte unter einem Namen zusammen. Fast jede Auswertung ist ein Durchlauf mit einer Zählschleife.
Reihung und Index
Feste Länge, ein Datentyp, Zugriff über den Index ab 0. Ein Index außerhalb von 0 … Länge − 1 führt zum Abbruch.
int[] a = new int[n];Durchlaufen
Die Zählschleife besucht jedes Element genau einmal. a.length statt einer festen Zahl schreiben; for-each nur zum Lesen.
for (int i = 0; i < a.length; i++)Summe, Zählen, Maximum
Akkumulator vor der Schleife anlegen: Summe mit 0, Zähler mit 0, Maximum mit dem ersten Element (nicht mit 0).
if (a[i] > max) max = a[i];Zweidimensional
Tabelle aus Zeilen und Spalten. Erst Zeile, dann Spalte; zwei verschachtelte Schleifen durchlaufen sie zeilenweise.
m[zeile][spalte]Bei m = new int[z][s] gilt m.length = z (Zeilen) und m[0].length = s (Spalten); insgesamt \(z\cdot s\) Elemente. Beispiel: 7 Wochentage × 24 Stunden = 168 Messplätze.
Ganzzahlige Division
Mit int summe und int n ist summe / n ganzzahlig: 17 / 4 = 4. Für den genauen Mittelwert erst umwandeln: (double) summe / n.
Suchen: linear oder binär
Die lineare Suche funktioniert immer, die binäre nur auf sortierten Daten — dafür wächst ihr Aufwand kaum, wenn die Datenmenge wächst.
Lineare Suche
Von vorn nach hinten vergleichen, beim ersten Treffer den Index zurückgeben, sonst −1. Ungünstigster Fall: alle \(n\) Elemente.
Binäre Suche
Mittleres Element des Suchbereichs ansehen; zu klein → rechts weitersuchen, zu groß → links. Der Bereich halbiert sich jedes Mal.
mitte = (links + rechts) / 2Voraussetzung
Die binäre Suche braucht eine sortierte Reihung. Auf unsortierten Daten liefert sie falsche Antworten, ohne abzustürzen.
Vergleich
Bei 1000 Werten höchstens 1000 gegen 10 Schritte, bei einer Million 1 000 000 gegen 20. Doppelt so viele Daten: linear doppelt, binär +1.
Die Schleife läuft, solange links ≤ rechts. Beispiel: \(n = 100\), \(2^6 = 64 \le 100 < 128\) → höchstens 7 angesehene Elemente.
Grenzen genau setzen
Nach dem Vergleich links = mitte + 1 bzw. rechts = mitte − 1. Mit links = mitte kann die Schleife endlos laufen, mit links < rechts wird das letzte Element nicht mehr geprüft.
Sortieren und vergleichen
Alle drei Verfahren sortieren an Ort und Stelle und brauchen im ungünstigsten Fall quadratisch viele Vergleiche. Sie unterscheiden sich bei Vertauschungen, Stabilität und vorsortierten Daten.
Selectionsort
Durchlauf \(i\): Minimum im Rest ab \(i\) suchen (Index merken), dann mit a[i] tauschen. Höchstens \(n-1\) Vertauschungen.
if (a[j] < a[min]) min = j;Insertionsort
Schlüssel a[i] zwischenspeichern, größere Elemente links davon eine Stelle nach rechts schieben, Schlüssel in die Lücke setzen.
while (j >= 0 && a[j] > key)Bubblesort
Benachbarte Paare vergleichen und vertauschen; nach Durchlauf \(k\) stehen die \(k\) größten Werte hinten. Ohne Tausch im Durchlauf: fertig.
if (a[j] > a[j + 1]) tausche(j, j + 1);Tauschen
Zum Vertauschen zweier Elemente wird eine Hilfsvariable gebraucht. Der Speicherbedarf bleibt unabhängig von \(n\) — nur diese eine Variable.
h = a[i]; a[i] = a[j]; a[j] = h;| Verfahren | Idee | Vergleiche | stabil? | vorsortiert |
|---|---|---|---|---|
| Selectionsort | Minimum des Rests nach vorn tauschen | immer \(\frac{n(n-1)}{2}\) | nein | kein Vorteil |
| Insertionsort | nächstes Element in den sortierten Teil einfügen | \(n-1\) bis \(\frac{n(n-1)}{2}\) | ja | sehr schnell |
| Bubblesort | Nachbarn vertauschen, Größtes wandert nach hinten | \(\frac{n(n-1)}{2}\), mit Abbruch ab \(n-1\) | ja | schnell mit Abbruch |
Quadratisches Wachstum: doppelt so viele Werte → etwa viermal so viele Vergleiche. Beispiel: \(n = 20\) → 190, \(n = 40\) → 780 Vergleiche.
Stabilität
Ein Verfahren ist stabil, wenn gleich große Elemente ihre Reihenfolge behalten. Selectionsort tauscht über andere Elemente hinweg und ist deshalb instabil.
Die Regeln, an denen die Punkte hängen
In Klausuren zu Reihungen gehen die meisten Punkte bei Grenzen, beim Zählen und bei unbegründeten Vergleichen verloren.
Regel 1 — Grenzen prüfen
Jede Schleife am ersten und letzten Durchlauf testen: Stimmen < oder <=? Wird a[i + 1] oder a[i − 1] gelesen, muss der Zählbereich um eins kürzer sein.
Regel 2 — Tracetabelle sauber führen
Eine Zeile pro Durchlauf bzw. Schritt, alle beteiligten Variablen als Spalten, nur Änderungen eintragen. Bei Sortierverfahren den Zustand nach jedem Durchlauf notieren.
Regel 3 — Zählen wie vereinbart
Vorher festhalten, was gezählt wird: Vergleiche zwischen Elementen, Vertauschungen oder Verschiebungen. Formeln mit einem kleinen Beispiel gegenprüfen, etwa \(n = 4\): \(3 + 2 + 1 = 6 = \frac{4\cdot3}{2}\).
Regel 4 — Effizienz begründen
Nicht nur „schneller“ schreiben, sondern mit Zahlen und Wachstum argumentieren: „Bei doppelter Datenmenge braucht die binäre Suche nur einen Schritt mehr, Selectionsort etwa viermal so viele Vergleiche.“ Auch den Speicherbedarf nennen.