Standardalgorithmen: Suche, lineare und binäre Suche, Sortierung, Bubblesort, Selection, Insertion
Suchen und Sortieren gehören zu den grundlegendsten Operationen in der Softwareentwicklung. In diesem Artikel lernst Du fünf wichtige Standardalgorithmen kennen: lineare Suche, binäre Suche, Bubblesort, Selection Sort und Insertion Sort. Für jeden Algorithmen erkläre ich die Funktionsweise, die Zeitkomplexität in Big-O-Notation und ein Codebeispiel in Python.
Egal ob AP1, Studium oder irgendeine andere IT-Ausbildung, Suchen und Sortieren wird immer “abgefragt” oder “erwartet”. Aber in der Regel nur einfache Bubblesorts oder vielleicht auch nur das Abfragen von Arrays oder das Sortieren von Arrays.
Du solltest Dur die wichtigsten Algorithmen anschauen, weil Sie Dir auch das Leben erleichtern.
Denn Zeit ist Geld und hier fängt das erste Programmierdilemma schon an. Ab wann ist ein Algorithmus gut, wann ist der unbrauchbar ?
Je größer die Daten sind, desto sinnvoller ist die richtige herangehensweise.
Während es bei kleinen Datenmengen “gefühlt” keinen Unterschied macht, ob du 0.2 Sekunden wartest, oder 0.5…
so kann es sich bei großen Datenmengen und viele Sekunden bis Minuten handeln.
Also bemessen wir Algorithmen nach … Geschwindigkeit. Unser Ziel ist es immer den schnellsten Algorithmus zu finden. Wir haben darüber bereits einen Artikel geschrieben, aber da es hier relavant ist, möchten wir es noch einmal kurz ewähnt haben:
Was bedeutet O(1), O(n), O(log n) und O(n²)?
Bevor wir die einzelnen Algorithmen betrachten, solltest Du verstehen, wie wir ihre Geschwindigkeit beschreiben. Dafür verwenden wir die Big-O-Notation. Sie sagt nicht, wie viele Millisekunden ein Algorithmus braucht, sondern wie stark die Laufzeit mit der Menge der Daten wächst.
Hier die wichtigsten Klassen im Überblick:
- O(1) – konstant: Die Laufzeit bleibt gleich, egal wie viele Daten vorhanden sind. Ein Beispiel ist der Zugriff auf ein Array-Element über einen Index.
- O(log n) – logarithmisch: Die Laufzeit wächst sehr langsam. Die binäre Suche halbiert in jedem Schritt den Suchbereich, deshalb ist sie O(log n).
- O(n) – linear: Die Laufzeit wächst proportional zur Datenmenge. Wenn Du 1.000 Elemente hast, brauchst Du etwa doppelt so lange wie bei 500 Elementen.
- O(n²) – quadratisch: Die Laufzeit wächst sehr schnell. Bei doppelter Datenmenge brauchst Du etwa vier Mal so lange. Viele einfache Sortieralgorithmen haben diese Komplexität.
Die Big-O-Notation beschreibt immer den Worst Case, also das ungünstigste Szenario. Das hilft Dir, die schlechteste Laufzeit abzuschätzen, die ein Algorithmus haben kann.
Eine detailliertere Erklärung findest Du im Artikel Big-O Notation: Laufzeitkomplexität und Effizienz O(1), O(n), O(log n) und in der Einführung zur Komplexitätsanalyse, Big-O, Such- und Sortieralgorithmen. Für die folgenden Algorithmen reicht es, wenn Du Dir unsere Auswertung anschaust und diese zwischen “GUT” und “WENIGER GUT” einschätzen kannst.
Lineare Suche
Die lineare Suche durchläuft eine Liste Element für Element, bis das gesuchte Element gefunden wird oder das Ende erreicht ist. Sie funktioniert auf sortierten und unsortierten Daten.
Du fängst also am Anfang einer Schlange an und gehst sie dann komplett durch, bis zum Ende. Vielleicht hast Du Glück, vielleicht ist es aber das letzte Element.
def lineare_suche(liste, ziel):
for index, wert in enumerate(liste):
if wert == ziel:
return index
return -1- Best Case: O(1) ( Gesuchtes Element ist weit vorne )
- Worst Case: O(n) ( …zum Schluß…)
- Average Case: O(n)
Die lineare Suche ist einfach, aber bei großen Datenmengen langsam.
Binäre Suche
Die binäre Suche halbiert den Suchbereich in jedem Schritt. Sie setzt voraus, dass die Liste sortiert ist. Im Vergleich zur linearen Suche ist sie bei großen Datenmengen deutlich schneller.
def binaere_suche(liste, ziel):
links = 0
rechts = len(liste) - 1
while links <= rechts:
mitte = (links + rechts) // 2
if liste[mitte] == ziel:
return mitte
if liste[mitte] < ziel:
links = mitte + 1
else:
rechts = mitte - 1
return -1- Best Case: O(1)
- Worst Case: O(log n)
- Average Case: O(log n)
Bei einer Million Elementen benötigt die binäre Suche im Worst Case nur etwa 20 Vergleiche.
Wie viele wären es bei der Linearen ? ;)
Bubblesort
Bubblesort vergleicht wiederholt benachbarte Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge stehen. Größere Elemente steigen dadurch nach und nach nach oben.
Dieser Algorithmus wird sehr gerne für Prüfungen oder einfachen Aufgaben genutzt.
Du solltest ihn Dir anschauen und später können.
def bubblesort(liste):
n = len(liste)
while True:
vertauscht = False
for i in range(n - 1):
if liste[i] > liste[i + 1]:
liste[i], liste[i + 1] = liste[i + 1], liste[i]
vertauscht = True
n -= 1
if not vertauscht:
break
return liste- Best Case: O(n)
- Worst Case: O(n²)
- Average Case: O(n²)
Bubblesort ist einfach zu verstehen, aber für große Datenmengen ineffizient.
Selection Sort
Selection Sort sucht in jedem Durchgang das kleinste Element im unsortierten Bereich und fügt es am Ende des sortierten Bereichs ein.
def selection_sort(liste):
n = len(liste)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if liste[j] < liste[min_index]:
min_index = j
liste[i], liste[min_index] = liste[min_index], liste[i]
return liste- Best Case: O(n²)
- Worst Case: O(n²)
- Average Case: O(n²)
Selection Sort ist einfach, aber immer quadratisch. Er macht weniger Vertauschungen als Bubblesort.
Insertion Sort
Insertion Sort fügt jedes Element an der richtigen Stelle in den bereits sortierten Bereich ein. Das Vorgehen ähnelt dem Sortieren einer Hand beim Kartenspiel.
def insertion_sort(liste):
for i in range(1, len(liste)):
aktuelles = liste[i]
j = i - 1
while j >= 0 and liste[j] > aktuelles:
liste[j + 1] = liste[j]
j -= 1
liste[j + 1] = aktuelles
return liste- Best Case: O(n)
- Worst Case: O(n²)
- Average Case: O(n²)
Insertion Sort ist besonders effizient, wenn die Liste bereits fast sortiert ist.
Vergleich der Such- und Sortier-Algorithmen
| Algorithmus | Typ | Best Case | Worst Case | Einsatzgebiet |
|---|---|---|---|---|
| Lineare Suche | Suche | O(1) | O(n) | Unsortierte kleine Datenmengen |
| Binäre Suche | Suche | O(1) | O(log n) | Sortierte große Datenmengen |
| Bubblesort | Sortierung | O(n) | O(n²) | Nur zu Lernzwecken |
| Selection Sort | Sortierung | O(n²) | O(n²) | Kleine Datenmengen, wenige Vertauschungen |
| Insertion Sort | Sortierung | O(n) | O(n²) | Fast sortierte Daten, kleine Listen |
Wann welchen Algorithmus verwenden?
Für die Suche gilt:
- Bei unsortierten Daten verwendest Du die lineare Suche.
- Bei sortierten Daten verwendest Du die binäre Suche.
Für die Sortierung gilt:
- Bubblesort eignet sich nur zum Lernen.
- Selection Sort ist einfach, aber langsam.
- Insertion Sort ist gut für kleine oder fast sortierte Datenmengen.
- Für große Datenmengen verwendest Du besser Quicksort, Mergesort oder Heapsort.
**Lineare Suche, binäre Suche, Bubblesort, Selection Sort und Insertion Sort bilden das Fundament für das Verständnis von Algorithmen und Datenstrukturen. Sie sind einfach, lehrreich und zeigen gut, wie Big-O die Laufzeit beschreibt. In der Praxis kommen bei großen Datenmengen schnellere Algorithmen zum Einsatz, aber das Verständnis dieser fünf Standardalgorithmen ist essenziell für jeden Entwickler. **
Buchempfehlungen zu Algorithmen und Datenstrukturen
Wenn Du Dich weiter mit Algorithmen und Datenstrukturen beschäftigen möchtest, empfehlen wir Dir die folgenden Bücher:
Algorithmen & Datenstrukturen
Bücher über Algorithmen, Komplexitätsanalyse, Datenstrukturen und algorithmische Sicherheit
Algorithmen: Eine Einführung von Thomas H. Cormen u.a.
Bei Amazon ansehenAffiliate-Link: Bei einem Kauf erhalten wir möglicherweise eine Provision.
Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People von Aditya Y. Bhargava
Bei Amazon ansehenAffiliate-Link: Bei einem Kauf erhalten wir möglicherweise eine Provision.
Algorithmen und Datenstrukturen: Eine systematische Einführung in die Programmierung von Gunter Saake, Kai-Uwe Sattler
Bei Amazon ansehenAffiliate-Link: Bei einem Kauf erhalten wir möglicherweise eine Provision.
FAQ: Standardalgorithmen, Suche und Sortierung
1. Was ist ein Standardalgorithmus?
2. Was ist der Unterschied zwischen Suche und Sortierung?
3. Was ist eine lineare Suche?
4. Wann verwendet man eine lineare Suche?
5. Was ist eine binäre Suche?
6. Warum ist die binäre Suche schneller als die lineare Suche?
7. Welche Voraussetzung braucht die binäre Suche?
8. Was ist Bubblesort?
9. Warum wird Bubblesort in der Praxis kaum verwendet?
10. Was ist Selection Sort?
11. Was ist Insertion Sort?
12. Was ist der Best Case von Insertion Sort?
13. Was bedeutet O(1)?
14. Was bedeutet O(n)?
15. Was bedeutet O(log n)?
16. Was bedeutet O(n²)?
17. Was ist der Worst Case?
Keine Sorge, einen Artikel über die Binäre Suche haben wir natürlich ebenfalls. Durch die FAQs kennst Du nun schon die Arbeitsweise.