Cheatsheet — selection sort

Snelle referentie. Klap open wat je nodig hebt.

Het algoritme zelf

Canonieke implementatie

def selection_sort(lijst):
    n = len(lijst)
    for i in range(n):
        min_index = i
        for j in range(i, n):
            if lijst[j] < lijst[min_index]:
                min_index = j
        lijst[i], lijst[min_index] = lijst[min_index], lijst[i]
    return lijst

Aflopend (groot → klein)

def selection_sort_aflopend(lijst):
    n = len(lijst)
    for i in range(n):
        max_index = i
        for j in range(i, n):
            if lijst[j] > lijst[max_index]:
                max_index = j
        lijst[i], lijst[max_index] = lijst[max_index], lijst[i]
    return lijst

Eén < → > en de variabelenaam. Verder identiek.

De bouwstenen

1. Index van kleinste vanaf positie

def index_van_kleinste_vanaf(lijst, start):
    min_index = start
    for i in range(start, len(lijst)):
        if lijst[i] < lijst[min_index]:
            min_index = i
    return min_index

2. Twee elementen swappen

# Pythonisch (één regel):
lijst[a], lijst[b] = lijst[b], lijst[a]

# Klassiek (drie regels, werkt in elke taal):
tijdelijk = lijst[a]
lijst[a] = lijst[b]
lijst[b] = tijdelijk

Python-syntax

range met startwaarde

range(start, stop)     # start, start+1, ..., stop-1
range(2, 5)            # 2, 3, 4 (geen 5!)
range(len(lijst))      # 0, 1, ..., len-1

Tuple-swap

a, b = b, a            # variabelen ruilen
lijst[i], lijst[j] = lijst[j], lijst[i]   # elementen ruilen

Geneste lussen

for i in range(n):          # buitenste lus
    for j in range(i, n):   # binnenste lus
        # voor elke combinatie van i en j ...

Totaal aantal iteraties: ongeveer n²/2.

Eigenschappen

Hoe snel?

• Beste, gemiddelde, slechtste geval: allemaal O(n²).
• Vergelijkingen: altijd n(n − 1)/2.
• Swaps: hoogstens n − 1 (één per ronde, soms minder).

Voor:

n	vergelijkingen	tijd op moderne CPU
100	4.950	< 1 ms
1.000	~500.000	~5 ms
10.000	~50 miljoen	~500 ms
100.000	~5 miljard	~50 seconden

Bij grote n is dit te traag.

Eigenschappen

• In-place: geen extra lijst nodig.
• Niet stabiel: gelijke elementen kunnen van volgorde wisselen.
• Voorspelbaar: zelfde aantal vergelijkingen op elke input.

Veelgemaakte fouten (snel)

Top-3 fouten

1. Zoeken vanaf index 0 i.p.v. vanaf i → vernielt al-gesorteerde deel.
2. Swap zonder tijdelijke variabele (lijst[a] = lijst[b]; lijst[b] = lijst[a]) → waarde gaat verloren.
3. range(0, n) in binnenste lus i.p.v. range(i, n) → onnodig werk én potentieel fout.

---

Klaar? Probeer ook bubble sort → — een andere manier om in O(n²) te sorteren, maar met meer swaps en minder uniforme vergelijkingen.