Sortier- und Suchalgorithmen verstehen
Kurzantwort
Sortieralgorithmen bringen Daten in eine Reihenfolge, Suchalgorithmen finden einen Wert darin. Bubblesort vertauscht benachbarte Elemente, bis alles sortiert ist – einfach, aber langsam. Die lineare Suche prüft jedes Element der Reihe nach; die binäre Suche halbiert den Bereich bei jedem Schritt, funktioniert aber nur auf sortierten Daten.
Teil des Lernpfads Programmieren und Softwareentwicklung · Schritt 7 von 18
Warum findet eine Datenbank einen Datensatz unter Millionen in Millisekunden? Weil sie clevere Such- und Sortierverfahren nutzt. Diese Grundalgorithmen sind Pflichtstoff für die Anwendungsentwicklung – und einfacher, als sie klingen.
Sortieren: Bubblesort
Bubblesort vergleicht benachbarte Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge stehen. Das wiederholt sich, bis kein Tausch mehr nötig ist – die größten Werte „blubbern" nach oben.
[5, 3, 8, 1] → vergleiche & tausche paarweise
[3, 5, 1, 8] → nächster Durchlauf
[3, 1, 5, 8] → …
[1, 3, 5, 8] → fertigSuchen: linear vs. binär
| Verfahren | Vorgehen | Voraussetzung | Tempo |
|---|---|---|---|
| Lineare Suche | jedes Element der Reihe nach prüfen | keine | langsam |
| Binäre Suche | Bereich halbieren, in der richtigen Hälfte weitersuchen | sortierte Daten | sehr schnell |
Die binäre Suche funktioniert wie das Suchen im Wörterbuch: In der Mitte aufschlagen, entscheiden „weiter vorne oder hinten?", die andere Hälfte verwerfen – und das wiederholen.
Suche 7 in [1, 3, 5, 7, 9, 11]
Mitte=5 → 7 ist größer → rechte Hälfte [7, 9, 11]
Mitte=9 → 7 ist kleiner → linke Hälfte [7]
gefunden!Die O-Notation kurz erklärt
Selbstkontrolle
Selbstkontrolle
Welche Voraussetzung muss erfüllt sein, damit die binäre Suche funktioniert?
Häufige Fragen
Warum lernt man Bubblesort, wenn er langsam ist?
Weil er das Prinzip des Sortierens besonders anschaulich zeigt: vergleichen und tauschen. Er eignet sich hervorragend, um Schleifen, Vergleiche und Durchläufe zu üben, und kommt genau deshalb in Prüfungen vor. In echter Software nutzt man die eingebauten, hochoptimierten Sortierfunktionen der Programmiersprache.
Wann ist die lineare Suche sinnvoll?
Immer dann, wenn die Daten nicht sortiert sind oder die Menge klein ist. Das Sortieren nur zum Zweck einer einzigen Suche würde sich nicht lohnen. Auch bei verketteten Listen, die keinen schnellen Zugriff über einen Index erlauben, ist die lineare Suche oft die praktikable Wahl.
Was bedeutet der schlimmste Fall bei einem Algorithmus?
Der schlimmste Fall (worst case) ist die ungünstigste Eingabe, etwa wenn das gesuchte Element ganz am Ende steht oder gar nicht vorkommt. Die O-Notation beschreibt meist genau diesen Fall, weil er eine verlässliche obere Schranke für die Laufzeit gibt. So weiß man, wie schlimm es maximal werden kann.
Muss ich Algorithmen auswendig programmieren können?
Du solltest ihr Prinzip erklären und in Pseudocode oder einem Struktogramm darstellen können, und den Ablauf an einem kleinen Beispiel durchspielen. Das exakte Auswendiglernen einer bestimmten Sprachsyntax ist weniger wichtig als das Verständnis, wie und warum der Algorithmus funktioniert.
Weiterlesen: Rekursion: wenn sich eine Funktion selbst aufruft · Variablen und Datentypen einfach erklärt
Das Wichtigste in Kürze
- Sortieren ordnet Daten, Suchen findet einen Wert darin.
- Bubblesort: benachbarte Elemente tauschen – einfach, aber
O(n²)(langsam). - Lineare Suche: alles der Reihe nach,
O(n), keine Voraussetzung. - Binäre Suche: halbieren,
O(log n), aber nur auf sortierten Daten. - O-Notation: beschreibt das Wachstum der Laufzeit, nicht die absolute Zeit.