In E3 wurden Programme vor allem als konkrete Anweisungsfolgen entwickelt: Variablen speichern Werte, Bedingungen steuern Entscheidungen, Schleifen wiederholen Schritte und Funktionen fassen Verhalten zusammen. Q1.2 hebt diese Erfahrung auf eine allgemeinere Ebene. Im Mittelpunkt steht nun nicht mehr nur, wie ein Programm formuliert wird, sondern welches Verfahren hinter dem Programm steht.
Ein Algorithmus wird hier als beschreibbare Strategie verstanden, die ein Problem für eine Klasse von Eingaben löst. Code ist eine mögliche Implementierung dieses Verfahrens, aber nicht das Verfahren selbst. Dieselbe Such- oder Sortieridee kann als Text, Struktogramm, Pseudocode oder Java-Code dargestellt werden.
Suche und Sortierung bilden den gemeinsamen Problemraum von Q1.2. An ihnen wird sichtbar, wie Datenstruktur, Voraussetzung, Schrittlogik, Korrektheit und Effizienz zusammenhängen: Man muss wissen, wonach gesucht wird, welche Ordnung Daten besitzen, wann ein Verfahren abbrechen darf und wie sein Aufwand mit der Eingabegröße wächst.
Die curriculare Grenze ist bewusst eng: Q1.2 führt keine allgemeine Algorithmik als eigenes Themenfeld aus. Der Algorithmusbegriff dient als Fundament, um Suchalgorithmen und Sortieralgorithmen fachlich beschreiben, implementieren und bewerten zu können.
Diese Unterscheidung wirkt zunächst klein, verändert aber die Blickrichtung. In E3 konnte eine Schleife vor allem als Sprachmittel verstanden werden: Sie wiederholt Anweisungen, solange eine Bedingung gilt. In Q1.2 wird gefragt, welche Rolle diese Wiederholung im Verfahren spielt. Bei einer Suche kann eine Schleife zum Beispiel nacheinander Indizes prüfen; bei einem Sortierverfahren kann sie wiederholt Vergleiche, Vertauschungen oder Verschiebungen auslösen.
Ein Verfahren muss nicht zuerst als Code erscheinen. Es kann in natürlicher Sprache beschrieben, als Struktogramm strukturiert, als Pseudocode präzisiert und erst danach implementiert werden. Entscheidend ist, dass die Schritte eindeutig bleiben: Welches Element wird betrachtet? Welcher Vergleich wird durchgeführt? Was passiert bei Treffer, Nicht-Treffer oder falscher Reihenfolge? Wann ist der Ablauf beendet?
Beginne beim ersten Element einer Liste. Vergleiche dieses Element mit dem Suchwert. Ist es gleich, ist der Treffer gefunden. Ist es nicht gleich, gehe zum nächsten Index. Wird das Ende der Liste erreicht, ohne dass ein Treffer gefunden wurde, ist der Suchwert nicht enthalten.
int linearSuche(int[] a, int suchwert) {
for (int i = 0; i < a.length; i++) {
if (a[i] == suchwert) return i;
}
return -1;
}Der Code ist ausführbar, aber seine fachliche Bedeutung ergibt sich aus dem Verfahren: indexweise prüfen, bei Treffer abbrechen, sonst Nicht-Treffer melden.
Das Struktogramm-Werkzeug kann genutzt werden, um diese Trennung sichtbar zu machen: Zuerst wird die Ablaufstruktur gelesen, dann werden Bedingung, Wiederholung und Rückgabe im Code wiedererkannt. So bleibt der Algorithmus als Verfahren im Blick, statt mit einer einzelnen Programmierschreibweise gleichgesetzt zu werden. Die beiden Suchverfahren werden im folgenden Abschnitt jeweils mit Struktogramm, Code und Beispiel gelesen.
Suchalgorithmen beantworten eine einfache Frage: Kommt ein bestimmter Wert in einer Datenmenge vor, und wenn ja, an welcher Stelle? In Q1.2 werden die Daten zunächst als Array oder als vergleichbare lineare Datenstruktur betrachtet. Ein Element ist über seinen Index erreichbar, und ein Suchwert wird durch Vergleiche mit gespeicherten Werten geprüft.
Die Stärke der linearen Suche liegt darin, dass sie fast keine Voraussetzung an die Daten stellt. Die Liste muss nicht sortiert sein, und es reicht, jedes Element nacheinander erreichen zu können. Der Ablauf ist deshalb gut als erstes Suchverfahren geeignet: Ein Index läuft von links nach rechts, jeder Schritt enthält genau einen Vergleich, und der Ablauf endet entweder beim Treffer oder nach dem letzten Element.
Das folgende Struktogramm zeigt diese Ablaufstruktur ohne Java-Syntax: Initialisierung, Wiederholung, Vergleich und die Entscheidung zwischen Treffer und Weitergehen werden als Verfahrensschritte lesbar.
Im Java-Code werden dieselben Rollen wiedererkennbar: Der Index steuert die Position,
der Vergleich prüft den Suchwert, ein Treffer bricht den Ablauf ab und ein Nicht-Treffer
führt am Ende zur Rückgabe -1.
int linearSuche(int[] a, int suchwert) {
int i = 0;
while (i < a.length) {
if (a[i] == suchwert) return i;
i++;
}
return -1;
}a = [14, 3, 9, 27, 18, 5, 11], Suche nach 18
Der Suchwert 18 wird zuerst mit dem Wert an Index 0 verglichen,
danach mit Index 1, dann mit Index 2 und Index 3.
Erst an Index 4 entsteht ein Treffer. Wäre der Wert nicht enthalten,
müsste das Verfahren bis zum Ende weiterlaufen und anschließend -1 melden.
Für die Laufzeit bedeutet das qualitativ: Je mehr Elemente im Array liegen, desto mehr Vergleiche können nötig werden. Im besten Fall steht der Suchwert direkt am Anfang. Im ungünstigen Fall steht er ganz hinten oder kommt gar nicht vor. Die Zahl der möglichen Vergleiche wächst dann ungefähr proportional zur Anzahl der Elemente.
Binäre Suche ist nicht einfach „die schnellere lineare Suche“. Sie ist eine andere Strategie und benötigt eine zentrale Voraussetzung: Die Daten müssen sortiert sein. Nur dann ist aus einem Vergleich mit dem mittleren Element ableitbar, ob der Suchwert links oder rechts davon liegen kann. Ohne Sortierung könnte ein gesuchter Wert fälschlich ausgeschlossen werden.
Der Suchraum ist der aktuell noch mögliche Bereich des Arrays. Zu Beginn umfasst er das gesamte Array. Nach jedem Vergleich mit der Mitte bleibt nur noch die linke oder rechte Hälfte übrig. Aus vielen einzelnen Prüfungen wird damit eine Folge von Halbierungen.
Das Struktogramm macht sichtbar, wie die Steuerung über links,
rechts und mitte funktioniert. Entscheidend ist nicht die
Schreibweise, sondern die Frage, welcher Bereich nach jedem Vergleich noch möglich ist.
Die Halbierung des Suchraums folgt direkt aus den Entscheidungen: Ist der mittlere
Wert zu klein, verschiebt sich links hinter die Mitte; ist er zu groß,
rückt rechts vor die Mitte.
int binaereSuche(int[] a, int suchwert) {
int links = 0;
int rechts = a.length - 1;
while (links <= rechts) {
int mitte = (links + rechts) / 2;
if (a[mitte] == suchwert) return mitte;
if (a[mitte] < suchwert) links = mitte + 1;
else rechts = mitte - 1;
}
return -1;
}a = [3, 7, 11, 14, 18, 24, 31], Suche nach 24
Der Suchraum beginnt bei den Indizes 0..6. Die Mitte liegt bei Index
3, dort steht 14. Weil 24 größer ist, kann die
linke Hälfte nicht mehr relevant sein. Der neue Suchraum ist 4..6.
Die Mitte dieses Bereichs ist Index 5, dort steht 24.
Der Treffer entsteht nach zwei Vergleichen.
Das Wachstum ist hier qualitativ logarithmisch: Wenn sich die Datenmenge verdoppelt, kommt ungefähr nur ein weiterer Halbierungsschritt hinzu. Genau darin liegt die besondere Effizienz der binären Suche. Zugleich zeigt sie bereits eine Denkbewegung, die in Q1.3 wieder aufgegriffen wird: Ein Problem wird durch Verkleinerung des Suchraums strukturiert. Die rekursive Modellierung dieser Idee gehört aber in Q1.3.
Sortieren bedeutet algorithmisch, Daten in eine festgelegte Ordnung zu bringen: Zahlen aufsteigend, Namen alphabetisch, Objekte nach einem Vergleichskriterium. Ein Sortieralgorithmus ist damit nicht nur eine Folge von Tauschbefehlen, sondern eine Strategie zur Herstellung von Ordnung. Für Q1.2 sind vor allem drei einfache Strategien wichtig: Selection Sort und Bubble Sort werden typischerweise, insbesondere im Worst Case, quadratisch bewertet. Insertion Sort ist im Worst Case ebenfalls quadratisch, kann bei fast sortierten Daten aber deutlich günstiger sein.
Die Begriffe sortierter und unsortierter Bereich helfen, den Ablauf zu lesen. Ein sortierter Bereich enthält die Elemente, deren Reihenfolge innerhalb des Verfahrens bereits feststeht. Ein unsortierter Bereich enthält die Elemente, die noch betrachtet, verglichen oder bewegt werden müssen. Die folgenden Verfahren unterscheiden sich darin, wie sie diese Bereiche aufbauen.
Selection Sort sucht im unsortierten Bereich das kleinste Element und setzt es an die nächste freie Position des sortierten Bereichs. Nach jedem Durchlauf ist eine weitere Position endgültig festgelegt. Die Strategie ist gut nachvollziehbar: erst auswählen, dann vertauschen.
Beim Startarray [9, 4, 7, 1, 6, 3] wird zuerst die 1
als Minimum gefunden und mit der ersten Position vertauscht. Danach wird im
Restbereich das nächste Minimum gesucht. Dadurch entstehen viele Vergleiche,
aber vergleichsweise wenige Vertauschungen.
Insertion Sort baut von links einen sortierten Bereich auf. Das nächste Element aus dem unsortierten Bereich wird herausgenommen und an der passenden Stelle in den sortierten Bereich eingefügt. Dafür müssen größere Elemente häufig nach rechts verschoben werden.
Beim Start [9 | 4, 7, 1, 6, 3] gilt die 9 zunächst als
sortierter Bereich. Die 4 wird davor eingefügt:
[4, 9 | 7, 1, 6, 3]. Danach wird die 7 zwischen
4 und 9 eingeordnet. Die Ordnung wächst Schritt für Schritt.
Bubble Sort betrachtet benachbarte Elemente. Stehen sie in falscher Reihenfolge, werden sie vertauscht. Nach einem vollständigen Durchlauf ist ein besonders großes Element nach rechts gewandert. Der sortierte Bereich entsteht also am rechten Rand, während der unsortierte Bereich von links her immer wieder durchlaufen wird.
Die Strategie ist anschaulich, aber oft aufwendig: Ein Element bewegt sich nur durch lokale Vertauschungen. Bei ungünstiger Reihenfolge können deshalb sehr viele Vergleiche und Vertauschungen entstehen.
Alle drei Verfahren können das gleiche Array sortieren, aber sie tun es mit unterschiedlicher Schrittlogik. Selection Sort fragt: „Welches Element gehört als nächstes nach vorne?“ Insertion Sort fragt: „Wo passt das nächste Element in den bereits sortierten Bereich?“ Bubble Sort fragt: „Stehen zwei Nachbarn falsch und müssen getauscht werden?“ Genau diese Strategieunterschiede sind die Grundlage für die spätere Laufzeitbewertung.
Effizienz wird in Q1.2 über Laufzeit aufgebaut. Gemeint ist nicht die gemessene Sekundenzeit auf einem bestimmten Computer. Bewertet wird, wie die Zahl relevanter Arbeitsschritte wächst, wenn die Eingabe größer wird. Bei Suchverfahren sind das vor allem Vergleiche mit dem Suchwert; bei Sortierverfahren sind es Vergleiche, Vertauschungen, Verschiebungen und Durchläufe.
Dadurch kann man Verfahren beurteilen, ohne sich auf eine konkrete Maschine oder Programmiersprache festzulegen. Eine Implementierung kann schneller oder langsamer geschrieben sein, aber die Grundfrage bleibt: Verdoppelt sich der Aufwand ungefähr mit der Eingabegröße, wächst er nur langsam durch Halbierungsschritte, oder steigt er durch verschachtelte Durchläufe deutlich stärker?
| Fall | Vergleiche bei Array-Länge n |
Bedeutung |
|---|---|---|
| Best Case | 1 |
Der Suchwert steht direkt am Anfang. |
| Worst Case | n |
Der Suchwert steht am Ende oder kommt gar nicht vor. |
| Average Case | ungefähr n / 2 |
Bei erfolgreicher Suche und gleichmäßig verteilter Trefferposition wird im Mittel etwa bis zur Mitte geprüft; bei erfolgloser Suche bleiben es n Vergleiche. |
Für Suchverfahren lässt sich der Unterschied anschaulich formulieren: Die lineare Suche schließt pro Schritt nur ein Element aus. Ihre Laufzeit wächst linear. Die binäre Suche halbiert den Suchraum. Ihre Laufzeit wächst logarithmisch, solange die Voraussetzung sortierter Daten erfüllt ist.
Bei einfachen Sortieralgorithmen liegt der Schwerpunkt der Bewertung auf der Laufzeit. Selection Sort, Insertion Sort und Bubble Sort enthalten typischerweise einen äußeren Fortschritt über Positionen und innere Vergleiche oder Bewegungen im Restbereich. Dadurch entsteht bei größeren Eingaben häufig quadratische Laufzeit: Verdoppelt man die Eingabegröße, kann der Aufwand deutlich stärker als doppelt wachsen.
| Verfahren | Typischer Bewertungsblick | Laufzeit qualitativ |
|---|---|---|
| Lineare Suche | Prüft Elemente nacheinander; keine Sortierung vorausgesetzt. | lineare Laufzeit |
| Binäre Suche | Halbiert den Suchraum; benötigt sortierte Daten. | logarithmische Laufzeit |
| Selection Sort | Sucht wiederholt ein Minimum im Restbereich. | quadratische Laufzeit |
| Insertion Sort | Verschiebt Elemente beim Einfügen in den sortierten Bereich. | typisch quadratisch, bei fast sortierten Daten oft günstiger |
| Bubble Sort | Vertauscht benachbarte Elemente über viele Durchläufe. | quadratische Laufzeit |
Die fachliche Bewertung lautet also nicht nur: „Das Verfahren funktioniert.“ Sie fragt: Welche Voraussetzung braucht es? Wie viele relevante Schritte entstehen? Welche Fälle sind günstig oder ungünstig? Und welches Verfahren ist für eine konkrete Datenlage angemessen?
Die einfachen Sortierverfahren arbeiten sehr lokal: Sie wählen ein Minimum aus, fügen ein einzelnes Element in einen sortierten Bereich ein oder vertauschen Nachbarn. Das ist didaktisch gut lesbar, skaliert aber bei großen Datenmengen oft schlecht. Auf erhöhtem Niveau wird deshalb ein effizienter Sortieralgorithmus betrachtet, der das Problem strukturell günstiger bearbeitet.
Quicksort kann dafür als Beispiel dienen. Die Grundidee ist, ein sogenanntes Pivot-Element zu wählen und die übrigen Werte danach zu trennen: kleinere Werte auf die eine Seite, größere Werte auf die andere. Danach werden die entstandenen Teilbereiche weiter geordnet. Typischerweise ist Quicksort effizient, wenn die Teilbereiche hinreichend ausgewogen entstehen. Bei ungünstiger Pivotwahl kann Quicksort aber ebenfalls quadratische Laufzeit erreichen.
[7, 2, 9, 4, 1, 8, 3]
Wird 4 als Pivot gewählt, lassen sich die Werte zunächst grob trennen:
[2, 1, 3] | 4 | [7, 9, 8]. Damit ist das Pivot bereits an der richtigen
relativen Stelle: Links stehen nur kleinere, rechts nur größere Werte. Der Gewinn
liegt nicht in einzelnen lokalen Nachbartauschen, sondern in einer Ordnung der
Datenbereiche.
Für Q1.2 reicht diese Grundidee aus: Effiziente Sortierverfahren nutzen eine andere Struktur als die einfachen Verfahren und können dadurch günstiger skalieren. Die genauere rekursive Beschreibung solcher Teilbereiche gehört in Q1.3.
Das Werkzeug Such- und Sortieralgorithmen visualisieren kann in Q1.2 als Analyseinstrument genutzt werden. Im Zentrum stehen lineare Suche, binäre Suche, Insertion Sort und auf erhöhtem Niveau Quicksort. Entscheidend ist nicht das bloße Abspielen einer Animation, sondern das begründete Lesen der Schritte: Welcher Vergleich findet statt? Welcher Index oder Suchraum ist aktiv? Welche Werte werden verschoben oder vertauscht?
Sinnvoll ist ein wiederkehrender Arbeitsweg: Zuerst wird eine Vermutung formuliert, welches Verfahren für eine Eingabe günstig ist. Danach wird dasselbe Array mit mehreren Verfahren untersucht. Die Vergleichszähler, sichtbaren Bewegungen und Kurvenverläufe werden anschließend genutzt, um die jeweilige Strategie zu begründen.
Rekursive Varianten des Werkzeugs sind für Q1.2 nur ein Ausblick. Ihre systematische Deutung, insbesondere über Teilprobleme und rekursive Aufrufe, gehört nach Q1.3.
Q1.2 endet mit einer fachlichen Einsicht: Algorithmen unterscheiden sich nicht nur darin, ob sie ein Problem lösen, sondern darin, wie sie Daten durchsuchen oder ordnen und wie ihr Aufwand mit der Eingabegröße wächst. Lineare Suche, binäre Suche und einfache Sortieralgorithmen machen diese Unterschiede an überschaubaren Verfahren sichtbar.
Q1.3 schließt daran an, verschiebt aber den Schwerpunkt. Dort wird gefragt, wie Verfahren nicht nur iterativ Schritt für Schritt, sondern rekursiv über Teilprobleme beschrieben werden können. Die in Q1.2 vorbereitete Idee der Suchraumverkleinerung bleibt dabei ein Anschluss, wird aber erst in Q1.3 als eigenes Rekursionskonzept ausgearbeitet.
Inhalte wie rekursive Grafiken, rekursive mathematische Funktionen, Terminierungsbedingungen rekursiver Aufrufe, Parameterübergabe, einfache und mehrfache Rekursion, Rekursion versus Iteration und Backtracking gehören daher nicht in die Ausarbeitung von Q1.2, sondern in die anschließende Rekursionsseite.