Ga naar hoofdinhoud

Er gaat iets mis — top-3 fouten

Leerdoel: je herkent de klassieke valkuilen bij selection sort.

Zoeken vanaf index 0 in plaats van vanaf i​

Geen foutmelding, maar wel een stille fout: de elementen die vooraan al goed stonden worden door nieuwe swaps overschreven.

Oorzaak: elke ronde zoek je nog steeds in de hele lijst — ook in het al gesorteerde stuk vooraan. En je swapt met lijst[i], wat een al-gesorteerde plek kan zijn. Het sorted-stuk wordt vernield.

Oplossing: zoek vanaf i en begin de zoektocht met min_index = i. Zo laat je het al-gesorteerde deel met rust.

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

# GOED
for i in range(n):
    min_index = i
    for j in range(i, n):
        ...

Verkeerde swap — informatie verliezen​

Oorzaak: je overschrijft lijst[a] met lijst[b] voordat je de oude waarde van lijst[a] ergens hebt bewaard. Daarna is de oude waarde weg.

Oplossing: gebruik een tijdelijke variabele, of de Pythonische tuple-swap.

# FOUT
lijst = [5, 2, 8, 1, 4]
a, b = 0, 3
lijst[a] = lijst[b]   # lijst[0] wordt 1; de 5 is weg
lijst[b] = lijst[a]   # lijst[3] wordt 1 (alweer)

# GOED (klassiek)
tijdelijk = lijst[a]
lijst[a] = lijst[b]
lijst[b] = tijdelijk

# GOED (Pythonisch)
lijst[a], lijst[b] = lijst[b], lijst[a]

Meer uitleg: Bouwsteen 2 — swappen.

Eén te kort: range(i, n - 1)​

Geen Python-foutmelding — de lijst komt er bijna goed uit, maar het laatste element doet niet mee.

Oorzaak: bij bubble sort hoort een - 1 in de lus, omdat je daar lijst[i + 1] bekijkt. Bij selection sort niet: de binnenste lus kijkt alleen naar lijst[j], dus j mag tot en met het laatste element gaan. Met range(i, n - 1) wordt het laatste element nooit als kleinste gevonden.

Oplossing: for j in range(i, n). Het laatste element hoort bij het ongesorteerde stuk.

def selection_sort_fout(lijst):
    n = len(lijst)
    for i in range(n):
        min_index = i
        for j in range(i, n - 1):    # FOUT: het laatste element doet niet mee
            if lijst[j] < lijst[min_index]:
                min_index = j
        lijst[i], lijst[min_index] = lijst[min_index], lijst[i]
    return lijst

print(selection_sort_fout([5, 2, 8, 1, 4]))   # [1, 2, 5, 8, 4]

De 4 achteraan is nooit bekeken en blijft staan. Met range(i, n) komt er [1, 2, 4, 5, 8] uit.

Door naar cheatsheet.