Bouw zelf — tel het aantal swaps

Leerdoel: je past selection sort aan om het werk te meten, en je ziet visueel hoeveel sneller of langzamer hij is bij verschillende soorten input.

Opdracht

Schrijf selection_sort_telt(lijst) die het aantal swaps returnt tijdens het sorteren.

Tel alleen echte swaps (i ≠ min_index). Verwacht:

• Op [3, 1, 2] → 2 echte swaps.
• Op [1, 2, 3] (al gesorteerd) → 0 echte swaps (elke ronde is i == min_index, dus geen ruil nodig).
• Op [3, 2, 1] (omgekeerd) → 1 echte swap (alleen ronde 0 ruilt de 3 en de 1; daarna staat alles al goed).

Test op drie typen lijst: al-gesorteerd, omgekeerd, en willekeurig. Plot het aantal swaps en vergelijkingen.

Python

Code-omgeving wordt voorbereid…

Tip

Twee dingen:

1. Voeg een if i != min_index: toe vóór de swap. Alleen dán daadwerkelijk swappen én swaps += 1 doen.
2. Initialiseer swaps = 0 vóór de buitenste lus.

Antwoord

def selection_sort_telt(lijst):
    n = len(lijst)
    swaps = 0
    vergelijkingen = 0
    for i in range(n):
        min_index = i
        for j in range(i, n):
            vergelijkingen += 1
            if lijst[j] < lijst[min_index]:
                min_index = j
        if i != min_index:
            lijst[i], lijst[min_index] = lijst[min_index], lijst[i]
            swaps += 1
    return swaps, vergelijkingen

Wat zie je in de grafiek?

Interpretatie

• Vergelijkingen zijn voor alle drie de soorten lijsten ongeveer gelijk — selection sort kijkt altijd door het hele ongesorteerde stuk. Bij n = 50: ongeveer 50·49/2 = 1225 vergelijkingen.
• Swaps verschillen wel:
  • Al gesorteerd → 0 echte swaps (i == min_index elke ronde).
  • Omgekeerd → ongeveer n/2 swaps.
  • Willekeurig → ergens daartussen.

Dat is het karakter van selection sort: voorspelbaar veel vergelijkingen, maar weinig swaps. Bij dure swaps (objecten ruilen op een trage opslag) is dat een voordeel.

Uitdaging (optioneel)

Pas selection sort aan zodat hij in elke ronde tegelijk de kleinste én grootste vindt. Zet de kleinste vooraan en de grootste achteraan — zo sorteer je in n / 2 rondes in plaats van n. (Variant: double-ended selection sort.)

Door naar stap 10: veelgemaakte fouten →