Bubble sort en insertion sort
Codeer beide kwadratische sorteeralgoritmen, begrijp waarom ze O(n²) zijn en herken het ene geval waarin insertion sort beter presteert dan merge sort.
Bubble sort en insertion sort is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Waarom O(n²)-sorteeralgoritmen bestuderen?
Bubblesort en invoegsortering kosten in het slechtste geval O(n), waardoor ze onpraktisch zijn voor grote invoer. Toch verwacht elk serieus algoritme-interview dat je ze kunt implementeren en analyseren. Ze leren je fundamentele concepten — vergelijken, verwisselen, stabiel sorteren en gedrag in het beste geval — die ook op geavanceerdere algoritmen van toepassing zijn. Interviewers gebruiken ze om te testen of je vanuit de eerste beginselen kunt redeneren over lusinvarianten en asymptotische notatie.
# 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')Bubblesort: het maximum omhoog laten komen
Bubblesort doorloopt de array herhaaldelijk en verwisselt aangrenzende elementen die niet in de juiste volgorde staan. Na elke volledige doorgang komt het grootste ongesorteerde element 'omhoog' naar zijn definitieve positie aan het einde. Na n-1 doorgangen is de hele array gesorteerd. De naam verwijst naar de manier waarop grotere elementen als bellen omhoog drijven. Het is het eenvoudigste sorteeralgoritme om uit te leggen, maar wordt in de praktijk zelden gebruikt.
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]Bubblesort met vroegtijdig stoppen
Een geoptimaliseerde bubblesort gebruikt een vlag swapped: als een volledige doorgang door de binnenste lus geen enkele verwisseling oplevert, is de array al gesorteerd en stoppen we vroegtijdig. Daardoor is de complexiteit in het beste geval O(n) bij al gesorteerde invoer — het enige echte voordeel van bubblesort. Zonder deze vlag voert het algoritme altijd O(n²) vergelijkingen uit. Deze optimalisatie voor vroegtijdig stoppen is wat interviewers controleren wanneer ze vragen naar verbeteringen voor bubblesort.
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 passComplexiteitsanalyse van bubblesort
De buitenste lus van bubblesort wordt n-1 keer uitgevoerd. De binnenste lus wordt per doorgang n-1-i keer uitgevoerd: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 vergelijkingen. Dit geeft O(n²) in het gemiddelde en in het slechtste geval. Met de vlag voor vroegtijdig stoppen daalt de complexiteit in het beste geval naar O(n) voor gesorteerde invoer. De ruimtecomplexiteit is O(1) — alleen voor het verwisselen is een tijdelijke variabele nodig. Bubblesort is stabiel: gelijke elementen behouden hun onderlinge volgorde, omdat we alleen strikt grotere elementen verwisselen.
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=5Invoegsortering: een gesorteerde hand opbouwen
Invoegsortering bootst het sorteren van een hand kaarten na: pak de volgende kaart (het element) en voeg deze in op de juiste positie tussen de al gesorteerde kaarten links ervan. De invariant is dat arr[0:i] altijd gesorteerd is. Schuif voor elk nieuw element de grotere elementen naar rechts om ruimte te maken. Dit algoritme werkt ter plaatse, is stabiel en kost in het slechtste geval O(n²), maar in het beste geval O(n) voor bijna gesorteerde gegevens.
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]Invoegsortering stap voor stap
Volg invoegsortering op [3, 1, 4, 2]: i=1, key=1, schuif 3 naar rechts → [1, 3, 4, 2]. i=2, key=4, geen verschuivingen → ongewijzigd. i=3, key=2, schuif eerst 4 en daarna 3 naar rechts → [1, 2, 3, 4]. Elk element wordt vergeleken met de elementen links ervan totdat we de juiste positie vinden. De binnenste while-lus voert de verschuivingen uit met toewijzingen (sneller dan verwisselen, omdat één toewijzing per verschuiving nodig is tegenover drie bij een verwisseling).
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]Invoegsortering op bijna gesorteerde gegevens
De grootste kracht van invoegsortering is de complexiteit O(n + inversies). Een inversie is een paar (i,j) waarvoor i < j maar arr[i] > arr[j]. Voor bijna gesorteerde arrays met slechts enkele inversies is invoegsortering uitzonderlijk snel — in de praktijk soms sneller dan samenvoegsortering dankzij de eenvoud en cachevriendelijke toegang. Python gebruikt om precies deze reden invoegsortering voor kleine deelarrays in Timsort.
# 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)Stabiliteit bij sorteren
Een sorteeralgoritme is stabiel als gelijke elementen na het sorteren hun oorspronkelijke onderlinge volgorde behouden. Zowel bubblesort als invoegsortering is stabiel — gelijke elementen worden nooit verwisseld. Stabiliteit is belangrijk wanneer je achtereenvolgens op meerdere sleutels sorteert: sorteer eerst stabiel op de secundaire sleutel en daarna stabiel op de primaire sleutel, zodat bij gelijke primaire waarden de volgorde van de secundaire sleutel behouden blijft. Ook samenvoegsortering is stabiel; heapsort en quicksort zijn dat over het algemeen niet.
# 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 => stableInvoegsortering met binair zoeken
De binnenste lus van invoegsortering vindt zowel de juiste positie als de elementen die moeten worden verschoven. Je kunt binair zoeken gebruiken om de positie te vinden in O(log i) vergelijkingen, maar verschuiven kost nog steeds O(i) tijd — de totale complexiteit blijft dus O(n²). Deze optimalisatie vermindert het aantal vergelijkingen (nuttig bij dure vergelijkingsfuncties), maar niet het totale aantal bewerkingen. Deze 'binaire invoegsortering' komt in Timsort voor bij kleine blokgroottes.
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]Bubblesort versus invoegsortering: wanneer gebruik je welke?
Formuleer deze vergelijking tijdens interviews zelfverzekerd: invoegsortering is strikt beter dan bubblesort — beide hebben in het slechtste geval O(n²) en gebruiken O(1) ruimte, maar invoegsortering voert minder schrijfoperaties uit (O(n+k) voor k inversies tegenover O(n²) voor bubblesort), is cachevriendelijker en is de praktische keuze voor kleine n (Timsort gebruikt dit algoritme). Het enige echte voordeel van bubblesort is de didactische eenvoud. Gebruik in productie altijd de ingebouwde sorteermethode van de taal.
# 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]Inversies tellen als maatstaf
Het aantal inversies in een array is gelijk aan het aantal paren (i,j) waarvoor i < j maar arr[i] > arr[j]. Invoegsortering voert precies evenveel verschuivingen uit als er inversies zijn — een nuttig inzicht. Voor het efficiënt tellen van inversies (O(n log n)) heb je een aangepaste samenvoegsortering nodig. Interviewers vragen soms als vervolgvraag bij sorteerdiscussies: 'Hoe bewust is je algoritme van inversies?'
# 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 invertedKorte controle
Controleer je begrip van de concepten uit deze les van Data Structures & Algorithms — Coding Interview Prep.
Samenvatting van de les
In deze les heb je geleerd: bubblesort voert n-1 doorgangen uit, waarbij tijdens elke doorgang het huidige maximum naar zijn definitieve positie komt, met O(n²) in het slechtste geval maar O(n) in het beste geval dankzij de vlag voor vroegtijdig stoppen, invoegsortering schuift elementen naar rechts om de huidige sleutel op de juiste gesorteerde positie in te voegen en kost O(n + inversies) tijd, waardoor het optimaal is voor bijna gesorteerde gegevens, en beide algoritmen zijn stabiel, gebruiken O(1) ruimte en hebben O(n²) in het slechtste geval — maar invoegsortering heeft in alle praktische situaties duidelijk de voorkeur boven bubblesort. Hierna implementeren we samenvoegsortering vanaf nul.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Bubble sort en insertion sort” gratis?
Ja — de volledige tekst van “Bubble sort en insertion sort” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Bubble sort en insertion sort”?
Codeer beide kwadratische sorteeralgoritmen, begrijp waarom ze O(n²) zijn en herken het ene geval waarin insertion sort beter presteert dan merge sort. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Bubble sort en insertion sort”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Bubble sort en insertion sort
- Merge sort: verdelen, sorteren, samenvoegen
- Quick sort en pivotselectie
- Sorteren zonder vergelijkingen en Python's sort()