Ga naar hoofdinhoud

Bouwsteen 3 — zoek vanaf een bepaalde positie

Leerdoel: je breidt de "vind index van kleinste"-functie uit zodat hij vanaf een gegeven startpositie zoekt — niet vanaf 0.

Waarom dit nodig is​

Na ronde k staan de eerste k elementen al goed. Daar hoef je niet opnieuw te zoeken; alleen de rest, vanaf index k, is nog interessant.

Wat we willen​

index_van_kleinste_vanaf(lijst, start) geeft de index van het kleinste element in lijst[start:]. Let op: die index telt vanaf het begin van de hele lijst, niet vanaf start.

Voorbeeld: lijst = [1, 2, 8, 5, 4], start = 1:

  • Zoekgebied: [2, 8, 5, 4] — staat op indexen 1, 2, 3, 4 van de hele lijst.
  • Kleinste daarin: de 2, op index 1 van de hele lijst.

Voorspel​

Wat denk je dat dit print?

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

lijst = [1, 2, 8, 5, 4]
print(index_van_kleinste_vanaf(lijst, 0))
print(index_van_kleinste_vanaf(lijst, 1))
print(index_van_kleinste_vanaf(lijst, 2))
print(index_van_kleinste_vanaf(lijst, 3))
Antwoord
0
1
4
4
  • Bij start=0 zoek je in de hele lijst en vind je de 1 op index 0.
  • Bij start=1 blijft [2, 8, 5, 4] over: de 2 op index 1.
  • Bij start=2 blijft [8, 5, 4] over: de 4 op index 4.
  • Bij start=3 blijft [5, 4] over, en de 4 staat nog steeds op index 4.

Run​

Python
Code-omgeving wordt voorbereid…

Wat is nieuw?​

Twee veranderingen ten opzichte van bouwsteen 1:

  1. De startwaarde is min_index = start en niet 0. Anders vergelijk je alles met lijst[0], een element dat je juist wilde overslaan.

  2. De lus is for i in range(start, len(lijst)): hij begint bij start en loopt tot het eind, dus alles ervóór blijft ongemoeid.

Experimenteer — wat als start te groot is?​

Python
Code-omgeving wordt voorbereid…
Wat doet start = 3 op een lijst van lengte 3?
  • min_index = 3 — maar lijst[3] bestaat niet. Pas op: we proberen dat pas te lezen als de lus iets doet.
  • range(3, 3) is leeg, dus de for-lus doet nul rondes.
  • We retourneren min_index = 3 zonder ooit lijst[3] aan te raken. Geen crash, maar wel een onzinnige index.

Voor selection sort is dit geen probleem — we roepen het nooit aan met start == len(lijst). Maar als robuuste functie zou je eventueel een check toevoegen.

Wat nu nog mist​

We hebben alle ingrediënten:

Nu nog in een lus zetten, en de hele lijst komt goed te staan.

Door naar bouwsteen 4: de buitenste lus.