Bubble Sort und Insertion Sort
Implementieren Sie beide Sortieralgorithmen mit quadratischer Laufzeit, verstehen Sie, warum sie O(n²) benötigen, und erkennen Sie den einen Fall, in dem Insertion Sort Merge Sort übertrifft.
Bubble Sort und Insertion Sort ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Warum O(n²)-Sortierverfahren lernen
Bubble Sort und Insertion Sort benötigen im schlimmsten Fall O(n²) Zeit und sind daher für große Eingaben unpraktisch. Trotzdem wird in jedem ernsthaften Algorithmus-Interview erwartet, dass Sie beide implementieren und analysieren können. Sie vermitteln grundlegende Konzepte wie Vergleiche, Vertauschungen, stabiles Sortieren und das Verhalten im Best Case – Konzepte, die auch auf fortgeschrittenere Algorithmen anwendbar sind. Interviewer verwenden sie, um zu prüfen, ob Sie Schleifeninvarianten und asymptotische Notation von Grund auf nachvollziehen können.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')Bubble Sort: Das Maximum nach oben blubbern lassen
Bubble Sort durchläuft das Array wiederholt und vertauscht benachbarte Elemente, die nicht in der richtigen Reihenfolge stehen. Nach jedem vollständigen Durchlauf „blubbert“ das größte noch nicht sortierte Element an seine endgültige Position am Ende. Nach n-1 Durchläufen ist das gesamte Array sortiert. Der Name leitet sich davon ab, dass größere Elemente wie Blasen nach oben steigen. Der Algorithmus ist am einfachsten zu beschreiben, wird in der Praxis aber nur selten verwendet.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]Bubble Sort mit vorzeitigem Abbruch
Eine optimierte Version von Bubble Sort verwendet ein swapped-Flag: Wenn ein vollständiger innerer Durchlauf keine Vertauschungen erzeugt, ist das Array bereits sortiert und der Algorithmus wird vorzeitig beendet. Dadurch ergibt sich für bereits sortierte Eingaben ein Best Case von O(n) – der einzige echte Vorteil von Bubble Sort. Ohne dieses Flag führt der Algorithmus immer O(n²) Vergleiche durch. Diese Optimierung durch vorzeitigen Abbruch wird von Interviewern erwartet, wenn sie nach Verbesserungen für Bubble Sort fragen.
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passKomplexitätsanalyse von Bubble Sort
Die äußere Schleife von Bubble Sort wird n-1-mal ausgeführt. Die innere Schleife läuft pro Durchlauf n-1-i-mal: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 Vergleiche. Daraus ergibt sich O(n²) im Average Case und im Worst Case. Mit dem Flag für den vorzeitigen Abbruch sinkt der Best Case bei sortierten Eingaben auf O(n). Die Speicherkomplexität beträgt O(1) – nur für die Vertauschung ist eine temporäre Variable erforderlich. Bubble Sort ist stabil: Gleiche Elemente behalten ihre relative Reihenfolge, da nur strikt größere Elemente vertauscht werden.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5Insertion Sort: Eine sortierte Kartenhand aufbauen
Insertion Sort ahmt das Sortieren einer Kartenhand nach: Nehmen Sie die nächste Karte (das nächste Element) und fügen Sie sie an der richtigen Position zwischen den bereits sortierten Karten links davon ein. Die Invariante lautet, dass arr[0:i] immer sortiert ist. Verschieben Sie für jedes neue Element größere Elemente nach rechts, um Platz zu schaffen. Dieser stabile In-Place-Algorithmus benötigt im Worst Case O(n²), im Best Case bei nahezu sortierten Daten jedoch O(n).
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]Insertion Sort Schritt für Schritt
Verfolgen Sie Insertion Sort für [3, 1, 4, 2]: i=1, key=1, 3 nach rechts verschieben → [1, 3, 4, 2]. i=2, key=4, keine Verschiebungen → unverändert. i=3, key=2, zunächst 4 und dann 3 nach rechts verschieben → [1, 2, 3, 4]. Jedes Element wird mit den Elementen links davon verglichen, bis seine richtige Position gefunden ist. Die innere while-Schleife führt die Verschiebungen mithilfe von Zuweisungen aus. Das ist schneller als Vertauschungen, da eine Verschiebung eine Zuweisung benötigt, eine Vertauschung dagegen drei.
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]Insertion Sort bei nahezu sortierten Daten
Die entscheidende Eigenschaft von Insertion Sort ist seine Komplexität von O(n + Inversionen). Eine Inversion ist ein Paar (i,j), für das i < j, aber arr[i] > arr[j] gilt. Bei nahezu sortierten Arrays mit nur wenigen Inversionen ist Insertion Sort extrem schnell – aufgrund seiner Einfachheit und des cachefreundlichen Zugriffs in der Praxis manchmal sogar schneller als Merge Sort. Pythons Timsort verwendet genau aus diesem Grund Insertion Sort für kleine Teil-Arrays.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)Stabilität beim Sortieren
Ein Sortieralgorithmus ist stabil, wenn gleiche Elemente nach dem Sortieren ihre ursprüngliche relative Reihenfolge beibehalten. Sowohl Bubble Sort als auch Insertion Sort sind stabil – sie vertauschen niemals gleiche Elemente. Stabilität ist wichtig, wenn Sie nacheinander nach mehreren Schlüsseln sortieren: Sortieren Sie zuerst stabil nach dem sekundären Schlüssel und anschließend stabil nach dem primären Schlüssel, damit die Reihenfolge des sekundären Schlüssels bei gleichen primären Schlüsseln erhalten bleibt. Auch Merge Sort ist stabil; Heap Sort und Quick Sort sind im Allgemeinen nicht stabil.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stableInsertion Sort mit binärer Suche
Die innere Schleife von Insertion Sort findet sowohl die richtige Position als auch die zu verschiebenden Elemente. Sie können eine binäre Suche verwenden, um die Position mit O(log i) Vergleichen zu finden, aber das Verschieben benötigt weiterhin O(i) Zeit – die Gesamtkomplexität bleibt daher O(n²). Die Optimierung reduziert die Anzahl der Vergleiche (nützlich bei aufwendigen Vergleichsfunktionen), nicht aber die Gesamtzahl der Operationen. Dieser „binäre Insertion Sort“ wird in Timsort für kleine Abschnittsgrößen verwendet.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]Bubble Sort oder Insertion Sort: Wann Sie welchen verwenden
Formulieren Sie diesen Vergleich in Interviews selbstbewusst: Insertion Sort ist Bubble Sort eindeutig überlegen – beide benötigen im Worst Case O(n²) Zeit und O(1) Speicher, aber Insertion Sort führt weniger Schreiboperationen aus (O(n+k) für k Inversionen gegenüber O(n²) bei Bubble Sort), ist cachefreundlicher und die praktische Wahl für kleine n (Timsort verwendet ihn). Der einzige echte Vorteil von Bubble Sort ist seine didaktische Einfachheit. In produktivem Code sollten Sie immer die eingebaute Sortierfunktion der jeweiligen Sprache verwenden.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]Inversionen als Maßzahl zählen
Die Anzahl der Inversionen in einem Array entspricht der Anzahl der Paare (i,j), für die i < j, aber arr[i] > arr[j] gilt. Insertion Sort führt genau so viele Verschiebungen aus, wie Inversionen vorhanden sind – eine nützliche Erkenntnis. Um Inversionen effizient in O(n log n) zu zählen, ist eine modifizierte Version von Merge Sort erforderlich. Interviewer fragen bei Gesprächen über Sortieralgorithmen manchmal als weiterführende Frage: „Wie gut berücksichtigt Ihr Algorithmus Inversionen?“
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedSchnelltest
Überprüfen Sie Ihr Verständnis der Konzepte aus dieser Lektion zu Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Bubble Sort führt n-1 Durchläufe aus, wobei in jedem Durchlauf das aktuelle Maximum an seine endgültige Position gebracht wird; im Worst Case benötigt der Algorithmus O(n²), mit dem Flag für den vorzeitigen Abbruch im Best Case jedoch O(n), Insertion Sort verschiebt Elemente nach rechts, um den aktuellen key an der richtigen sortierten Position einzufügen, und benötigt O(n + Inversionen), wodurch der Algorithmus für nahezu sortierte Daten optimal ist, und beide Algorithmen sind stabil, benötigen O(1) Speicher und haben O(n²) im Worst Case – Insertion Sort wird jedoch in allen praktischen Szenarien Bubble Sort eindeutig vorgezogen. Als Nächstes implementieren wir Merge Sort von Grund auf.
Häufig gestellte Fragen
Ist die Lektion „Bubble Sort und Insertion Sort“ kostenlos?
Ja — der vollständige Text von „Bubble Sort und Insertion Sort“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Bubble Sort und Insertion Sort“?
Implementieren Sie beide Sortieralgorithmen mit quadratischer Laufzeit, verstehen Sie, warum sie O(n²) benötigen, und erkennen Sie den einen Fall, in dem Insertion Sort Merge Sort übertrifft. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Bubble Sort und Insertion Sort“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Bubble Sort und Insertion Sort
- Merge Sort: Teilen, sortieren, zusammenführen
- Quick Sort und Pivot-Auswahl
- Nicht vergleichende Sortierverfahren und Pythons sort()