💻 Programmeeroefening – Behoud de originele lijst

In deze oefening ga je een lijst sorteren zonder de oorspronkelijke lijst te veranderen.

In plaats van elementen te verplaatsen (zoals bij insertion sort), ga je een nieuwe lijst opbouwen waarin je telkens het juiste volgende element toevoegt.

---

🧠 Idee achter het algoritme

Dit lijkt op selection sort, maar met een belangrijk verschil:

👉 Je maakt een nieuwe, lege lijst en vult die stap voor stap.

Hoe?

• Je zoekt telkens het kleinste element dat je nog niet gebruikt hebt.
• Dat voeg je toe aan je nieuwe lijst.
• Daarna zoek je het volgende element dat iets groter is, enzovoort.

---

🛠 Wat moet je doen?

Schrijf de functie:

selection_sort(lijst)

Die:

1. Een nieuwe lege lijst maakt (bijvoorbeeld gesorteerd = [])
2. Stap voor stap de juiste elementen toevoegt aan deze lijst
3. Op het einde de nieuwe gesorteerde lijst teruggeeft

🚫 De originele lijst lijst mag je niet aanpassen.

---

🔧 Hulpfunctie die je moet gebruiken

Je kan gebruikmaken van de oplossing van vorige oefening:

def kleinste_element_groter_dan(lijst, ondergrens):
    kleinste_index = None
    for i in range(len(lijst)):
        if ondergrens is None or lijst[i] > ondergrens:
            if kleinste_index is None or lijst[i] < lijst[kleinste_index]:
                kleinste_index = i
    return kleinste_index

Deze functie helpt je enorm:

• Ze geeft de index van het kleinste element dat groter is dan waarde
• Als waarde = None, krijg je het kleinste element van de hele lijst

---

🔁 Hoe bouw je de oplossing op?

Denk in stappen:

1. Start met waarde = None 👉 Je zoekt dus het allerkleinste element

2. Gebruik de hulpfunctie om de index van dat element te vinden

3. Voeg dat element toe aan je nieuwe lijst

4. Bewaar de waarde van dat element als nieuwe waarde

5. Zoek nu het volgende element dat groter is dan deze waarde

6. Herhaal dit tot je alle elementen hebt toegevoegd

---

🧪 Voorbeeld stap voor stap

selection_sort([7, 3, 9, 5])

We bouwen een nieuwe lijst op:

• Start: gesorteerd = [], waarde = None

1. Zoek kleinste → 3 → voeg toe
   gesorteerd = [3], waarde = 3

2. Zoek kleinste > 3 → 5 → voeg toe
   gesorteerd = [3, 5], waarde = 5

3. Zoek kleinste > 5 → 7 → voeg toe
   gesorteerd = [3, 5, 7], waarde = 7

4. Zoek kleinste > 7 → 9 → voeg toe
   gesorteerd = [3, 5, 7, 9]

Resultaat:

[3, 5, 7, 9]

---

⚠️ Belangrijk om te begrijpen

• Je gebruikt de originele lijst enkel om te lezen, niet om te veranderen.
• Je houdt zelf bij wat het “laatst gekozen element” is (waarde).
• Je bouwt de oplossing volledig op in een nieuwe lijst.

---

💡 Tip: denk niet “ik sorteer de lijst”, maar “ik kies telkens het volgende juiste element en leg het in een nieuwe rij”.