Beim Sortieren von Daten gibt es viele Wege zum Ziel – einige schnell, andere langsam, manche elegant, andere eher simpel. In diesem Artikel werden Bubble Sort, Quick Sort, Heap Sort, Selection Sort und Merge Sort einfach und anschaulich erklärt.
🫧 1. Bubble Sort
📖 Theorie:
Bubble Sort vergleicht jedes benachbarte Element und tauscht sie, wenn sie in der falschen Reihenfolge sind. Das größte Element „wandert“ bei jedem Durchgang nach oben, wie eine Blase. Dieser Vorgang wird so lange wiederholt, bis das gesamte Array sortiert ist.
💻 Beispielcode:
def bubble_sort(arr):
n = len(arr)
# Äußere Schleife für jeden Durchgang
for i in range(n):
# Innere Schleife für den Vergleich benachbarter Elemente
for j in range(0, n - i - 1):
# Wenn das linke Element größer ist, tausche die beiden
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# Beispiel
zahlen = [5, 3, 8, 4, 2]
print(bubble_sort(zahlen)) # Ausgabe: [2, 3, 4, 5, 8]⏱️ Laufzeit:
- Durchschnitt: O(n²)
- Schlechtester Fall: O(n²)
- Bester Fall: O(n) (wenn das Array schon sortiert ist)
⚡ 2. Quick Sort
📖 Theorie:
Quick Sort ist ein sogenannter „Teile-und-herrsche“-Algorithmus. Das große Problem (unsortierte Liste) wird immer wieder in kleinere Teilprobleme zerlegt, bis diese einfach zu lösen sind.
Quick Sort ist dabei besonders schnell und effizient und wird in vielen Programmiersprachen standardmäßig verwendet.
🎯 Wie funktioniert Quick Sort Schritt für Schritt?
- 📌 Pivot auswählen
- 🪄 Liste in kleinere und größere Elemente aufteilen
- 🔁 Rekursiv sortieren
- 🛠️ Zusammenfügen
👉 Beispiel:
Liste: [5, 3, 8, 4, 2] → Pivot = 5
Links: [3, 4, 2] | Pivot: 5 | Rechts: [8]
💻 Beispielcode:
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = random.choice(arr)
kleiner = [x for x in arr if x < pivot]
gleich = [x for x in arr if x == pivot]
größer = [x for x in arr if x > pivot]
return quick_sort(kleiner) + gleich + quick_sort(größer)
# Beispiel
zahlen = [5, 3, 8, 4, 2]
print(quick_sort(zahlen)) # Ausgabe: [2, 3, 4, 5, 8]⏱️ Laufzeit:
- Durchschnitt: O(n log n)
- Schlechtester Fall: O(n²) (bei schlechter Pivot-Wahl)
- Bester Fall: O(n log n)
🏗️ 3. Heap Sort
📖 Theorie:
Heap Sort nutzt eine spezielle Datenstruktur – den Heap. Ein Heap ist ein Baum, bei dem jedes Elternelement größer (Max-Heap) oder kleiner (Min-Heap) als seine Kindknoten ist. Ziel ist es, das größte Element schnell an den Anfang (bzw. das Ende) des Arrays zu bringen.
🎯 Wie funktioniert Heap Sort Schritt für Schritt?
- Heap bauen:
Die Liste wird in einen Max-Heap umgewandelt. Das größte Element steht dann ganz oben. - Größtes Element entfernen:
Das oberste Element wird ans Ende des Arrays getauscht. - Heap verkleinern:
Die Größe des Heaps wird reduziert und die Struktur wiederhergestellt (Heapify). - Wiederholen:
Dies wird solange wiederholt, bis der Heap leer ist.
💻 Beispielcode:
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
# Prüfen, ob linkes Kind größer ist
if left < n and arr[left] > arr[largest]:
largest = left
# Prüfen, ob rechtes Kind größer ist
if right < n and arr[right] > arr[largest]:
largest = right
# Wenn das größte Element nicht an Position i ist, tauschen und weiter heapify
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Max-Heap bauen
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Elemente aus dem Heap sortieren
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Größtes Element ans Ende tauschen
heapify(arr, i, 0)
return arr
# Beispiel
zahlen = [5, 3, 8, 4, 2]
print(heap_sort(zahlen)) # Ausgabe: [2, 3, 4, 5, 8]⏱️ Laufzeit:
- Durchschnitt: O(n log n)
- Schlechtester Fall: O(n log n)
- Bester Fall: O(n log n)
🎯 4. Selection Sort
📖 Theorie:
Selection Sort sucht in jedem Durchgang das kleinste Element im unsortierten Teil des Arrays und tauscht es an die richtige Stelle nach vorne.
🎯 Wie funktioniert Selection Sort Schritt für Schritt?
- Das kleinste Element im gesamten Array suchen.
- Mit dem ersten Element tauschen.
- Das kleinste Element im restlichen (unsortierten) Teil suchen.
- Mit dem nächsten Element tauschen.
- Solange wiederholen, bis das Array sortiert ist.
👉 Selection Sort ist einfach, aber leider ineffizient bei großen Datenmengen.
💻 Beispielcode:
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# Beispiel
zahlen = [5, 3, 8, 4, 2]
print(selection_sort(zahlen)) # Ausgabe: [2, 3, 4, 5, 8]⏱️ Laufzeit:
- Durchschnitt: O(n²)
- Schlechtester Fall: O(n²)
- Bester Fall: O(n²)
🛠️ 5. Merge Sort
📖 Theorie:
Merge Sort ist ebenfalls ein „Teile-und-herrsche“-Algorithmus, ähnlich wie Quick Sort, aber garantiert immer eine gute Laufzeit.
🎯 Wie funktioniert Merge Sort Schritt für Schritt?
- Die Liste wird in zwei Hälften geteilt.
- Jede Hälfte wird rekursiv sortiert.
- Die beiden sortierten Hälften werden zusammengeführt (Merge).
👉 Der Vorteil: Die Teilung ist immer gleichmäßig, was die Laufzeit stabil hält.
💻 Beispielcode:
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
# Elemente der beiden Listen zusammenführen
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Restliche Elemente anhängen
result.extend(left[i:])
result.extend(right[j:])
return result
# Beispiel
zahlen = [5, 3, 8, 4, 2]
print(merge_sort(zahlen)) # Ausgabe: [2, 3, 4, 5, 8]⏱️ Laufzeit:
- Durchschnitt: O(n log n)
- Schlechtester Fall: O(n log n)
- Bester Fall: O(n log n)
📚 Fazit: Sortieralgorithmen im Vergleich
| Kriterium | Bubble Sort | Quick Sort | Heap Sort | Selection Sort | Merge Sort |
|---|---|---|---|---|---|
| Geschwindigkeit | Langsam | Sehr schnell | Schnell | Langsam | Schnell |
| Durchschnitts-Laufzeit | O(n²) | O(n log n) | O(n log n) | O(n²) | O(n log n) |
| Speicherbedarf | Gering | Gering | Gering | Gering | Hoch (zusätzlicher Speicher wird benötigt) |
| Arbeitsweise | Vergleichen & Tauschen | Pivot wählen & aufteilen | Heap-Datenstruktur | Kleinstes Element finden | Teilen & Zusammenfügen |
| Worst-Case | O(n²) | O(n²) | O(n log n) | O(n²) | O(n log n) |
💡 Zusammenfassung:
- Bubble Sort: Einfach zu verstehen, aber ineffizient.
- Quick Sort: Sehr effizient, wenn das Pivot gut gewählt wird.
- Heap Sort: Stabil und speichereffizient.
- Selection Sort: Einfach, aber nicht empfehlenswert für große Datenmengen.
- Merge Sort: Sehr zuverlässig mit stabiler Laufzeit, braucht aber zusätzlichen Speicher.
Wenn du große Datenmengen sortieren möchtest, sind Quick Sort, Heap Sort oder Merge Sort die besten Optionen. Bubble Sort und Selection Sort sind eher für Lernzwecke geeignet.
