# Domein B — Grondslagen ## B1.2 Standaardalgoritmen Sorteren en het **kortste pad** vinden --- ## Lesdoelen Na deze les: - ken je **BubbleSort, MergeSort en QuickSort**; - weet je wanneer een sorteeralgoritme goed toepasbaar is; - ken je de werking van het **kortstepadalgoritme van Dijkstra**. --- ## Standaardalgoritmen Voor veel voorkomende problemen bestaan al bekende algoritmen. Vandaag bekijken we: - drie algoritmen om gegevens te **sorteren**; - één algoritme om een **kortste pad** te vinden. > Waarom steeds opnieuw een oplossing bedenken als een goed algoritme al bestaat? --- ## BubbleSort Start met: **6 – 9 – 5 – 2 – 3** - Vergelijk steeds twee **naast elkaar liggende** waarden. - Staan ze verkeerd? **Wissel** ze om. - Ga door tot het einde van de lijst. - Herhaal dit totdat er niets meer hoeft te wisselen. > Grote waarden 'bubbelen' zo naar rechts. --- ## BubbleSort — eerste ronde Start: **6 – 9 – 5 – 2 – 3** Vergelijk van links naar rechts: **6–9** → niets doen **9–5** → wissel → **6 – 5 – 9 – 2 – 3** > De grootste waarde schuift steeds verder naar rechts. --- ## BubbleSort — eerste ronde (vervolg) Ga verder met: **6 – 5 – 9 – 2 – 3** **9–2** → wissel → **6 – 5 – 2 – 9 – 3** **9–3** → wissel → **6 – 5 – 2 – 3 – 9** > Na één volledige ronde staat de **9** zeker op de juiste plek. --- ## MergeSort Start met: **6 – 9 – 5 – 2 – 3** 1. Verdeel de lijst steeds in kleinere delen. 2. Ga door tot de delen eenvoudig te sorteren zijn. 3. Voeg de delen daarna **gesorteerd** weer samen. > Eerst **verdelen**, daarna **samenvoegen**. --- ## Divide and conquer MergeSort en QuickSort zijn **divide-and-conqueralgoritmen**.  <!-- .element: style="width: 62%;" --> **Divide → Conquer → Combine** --- ## QuickSort Start met: **6 – 9 – 5 – 2 – 3** - Kies een waarde als **pivot**. - Zet kleinere waarden aan de ene kant. - Zet grotere waarden aan de andere kant. - Herhaal dit voor de ontstane delen. > De keuze van de pivot beïnvloedt hoe het algoritme verloopt. --- ## Welk sorteeralgoritme? De efficiëntie hangt af van de **invoer**: - veel of weinig elementen; - al gedeeltelijk gesorteerd; - veel dubbele elementen. | | 50 elementen | Grotendeels gesorteerd | Veel dubbele elementen | |---|---|---|---| | **BubbleSort** | Niet efficiënt | Efficiënt | Niet efficiënt | | **MergeSort** | Efficiënt | Niet efficiënt | Efficiënt | | **QuickSort** | Efficiënt | Niet efficiënt | Niet efficiënt | --- ## Check: sorteren !!!vraag mc Een lijst is al grotendeels gesorteerd. Welk algoritme is volgens het overzicht het meest geschikt? - BubbleSort - MergeSort - QuickSort !!! --- <!-- .slide: class="section" --> # Van sorteren naar routes ## Hoe vindt een computer het kortste pad? --- ## Routeplanning Voor routeplanning kun je een **kortstepadalgoritme** gebruiken. Zo'n algoritme werkt meestal met een **gewogen graaf**: - plaatsen worden **knopen**; - verbindingen worden **lijnen**; - afstanden worden **gewichten**.  <!-- .element: style="width: 48%;" --> --- ## Van kaart naar graaf  <!-- .element: style="width: 58%;" --> > We zoeken het kortste pad van **Den Helder naar Rotterdam**. --- ## Dijkstra — de werkwijze 1. Geef de startplaats afstand **0**; alle andere plaatsen krijgen **∞**. 2. Kies de onbezochte plaats met de **kleinste bekende afstand**. 3. Bereken via die plaats de afstanden naar direct verbonden onbezochte plaatsen. 4. Is een nieuwe afstand kleiner? **Vervang** de oude waarde. 5. Markeer de plaats als bezocht en herhaal. --- ## Dijkstra — start  <!-- .element: style="width: 76%;" --> > Eerst zijn alle afstanden onbekend. Den Helder wordt het startpunt met afstand **0**. --- <!-- .slide: class="columns" --> ## Dijkstra — via Amsterdam Vanuit Amsterdam vinden we: - Den Haag: **90 + 55 = 145** - Utrecht: **90 + 50 = 140** |||  --- <!-- .slide: class="columns" --> ## Dijkstra — via Utrecht Via Utrecht wordt Rotterdam voorlopig: **140 + 60 = 200** > Maar voorlopig betekent nog niet dat dit de kortste route is. |||  --- <!-- .slide: class="columns" --> ## Dijkstra — via Den Haag Via Den Haag vinden we voor Rotterdam: **145 + 25 = 170** 170 is kleiner dan 200, dus we **vervangen** de afstand. |||  --- <!-- .slide: class="columns" --> ## De kortste route terugvinden Volg vanaf Rotterdam steeds de **vorige plaats** terug: **Rotterdam → Den Haag → Amsterdam → Den Helder** Dus vanaf Den Helder: **Den Helder → Amsterdam → Den Haag → Rotterdam = 170 km** |||  --- ## Check: Dijkstra !!!vraag mc Je vindt via een nieuwe route een afstand van 170. In de tabel stond 200. Wat doe je volgens Dijkstra? - Je houdt 200, want die stond er eerder. - Je vervangt 200 door 170. - Je telt 170 en 200 bij elkaar op. - Je markeert meteen alle plaatsen als bezocht. !!! --- ## Afsluiting Kun je nu uitleggen: 1. hoe **BubbleSort** werkt? 2. wat **divide and conquer** betekent bij MergeSort en QuickSort? 3. waarom de invoer invloed heeft op de keuze van een sorteeralgoritme? 4. hoe **Dijkstra** stap voor stap een kortste pad vindt?