💻 Programmeeroefening – Efficiënter sorteren: Insertion Sort

In deze oefening ga je een volledige lijst sorteren met het algoritme Insertion Sort.

Je bouwt stap voor stap een gesorteerde rij op, net zoals wanneer je leerlingen één voor één op de juiste plaats in een rij zet.

🧠 Idee achter het algoritme

Je kan de lijst opdelen in twee delen:

  • 🔵 Linker deel (gesorteerd deel)
    Dit deel is al correct van klein naar groot.

  • 🟡 Rechter deel (nog niet verwerkt)
    Deze elementen moeten nog één voor één op de juiste plaats gezet worden.

In het begin is alleen het eerste element al “gesorteerd” (want één element is altijd al in orde).

🛠 Wat moet je doen in de functie?

Schrijf de functie:

insertion_sort(rij)

Die werkt als volgt:

  1. Start bij het tweede element van de lijst (index 1).

  2. Neem dat element en beschouw het als de “zittende leerling” die op zijn plaats moet komen.

  3. Gebruik de functie:

    wissel_tot_juiste_plaats(rij, positie)

    om dat element op de juiste plaats te zetten in het gesorteerde deel links.

  4. Ga daarna naar het volgende element (positie + 1).

  5. Herhaal dit tot je alle elementen hebt behandeld.

🔁 Belangrijk om te begrijpen

  • Je sorteert niet alles in één keer.
  • Je bouwt de oplossing stap voor stap op.
  • Na elke stap is het linker deel van de lijst steeds groter en correct gesorteerd.

📌 Hulpfunctie die je moet gebruiken

Je mag de oplossing van de vorige oefening gebruiken (kopieer en plak ze volledig in de editor hieronder):

wissel_tot_juiste_plaats(rij, positie_zittend)

👉 Deze functie zorgt ervoor dat het element op positie_zittend naar links schuift tot het op de juiste plaats staat.

🧪 Voorbeeld

insertion_sort([20, 40, 10, 30])

Stap voor stap gebeurt dit:

  • Start: [20, 40, 10, 30]
  • 10 wordt ingevoegd → [10, 20, 40, 30]
  • 30 wordt ingevoegd → [10, 20, 30, 40]

Resultaat:

[10, 20, 30, 40]

💡 Tip: denk telkens “ik voeg één leerling toe aan een al nette rij en zet hem op de juiste plaats”.