QuickSort

QuickSort
1 / 16
volgende
Slide 1: Tekstslide
InformaticaMiddelbare schoolhavo, vwoLeerjaar 4-6

In deze les zitten 16 slides, met interactieve quizzen en tekstslides.

time-iconLesduur is: 50 min

Onderdelen in deze les

QuickSort

Slide 1 - Tekstslide

Leerdoel
Aan het eind van deze les ken je het principe van het QuickSort algoritme en kan je elementen uit een lijst sorteren aan de hand van het QuickSort algoritme.

Slide 2 - Tekstslide

Wat bepaalt in de verdeelfase van MergeSort het aantal stappen dat je moet nemen?
A
De mate waarin de lijst al gesorteerd is.
B
Het aantal elementen van de lijst.
C
De hoeveelheid dezelfde elementen in de lijst.
D
In hoeverre de lijst steeds in twee even grote lijsten kan worden opgedeeld.

Slide 3 - Quizvraag

Leg uit waarom er bij het MergeSort-algoritme nauwelijks verschil is tussen het bestcase- en worstcasescenario.

Slide 4 - Open vraag

Bekijk de volgende lijst met elementen. Kun je deze lijst het snelst sorteren met BubbleSort of met MergeSort?

2 1 4 5 6 5 9 8
A
BubbleSort
B
MergeSort

Slide 5 - Quizvraag

Wat bedoelen we met divide-and-conquermethode?

Slide 6 - Open vraag

QuickSort
Het QuickSort algoritme maakt net zoals het MergeSort algoritme gebruik van de divide-and-conquermethode.

Door de werking van het QuickSort algoritme pakt onder andere de worstcasescenario van QuickSort minder slecht uit dan dat van MergeSort.

Slide 7 - Tekstslide

Werking QuickSort
  1. Kies een willekeurig element uit de lijst. Dit element wordt de pivot genoemd.

  2. Verplaats de elementen als volgt:

    a. Elementen met een waarde kleiner of gelijk aan de pivot komen links van de pivot.
    b. Elementen met een waarde groter dan de pivot komen rechts van de pivot.

  3. Voer stappen 1 en 2 uit op de deellijsten links en rechts van de pivot.

  4. Herhaal stap 3 totdat alles gesorteerd is.

Slide 8 - Tekstslide

Voorbeeld
Sorteer de volgende elementen. Kies als pivot steeds het meest linker element. Schrijf alle stappen uit!

5  3  8  2  7  1

Slide 9 - Tekstslide

Antwoord
Sorteer de volgende elementen. Kies als pivot steeds het meest linker element.

5  3  8  2  7  1


Slide 10 - Tekstslide

Oefenvraag 1
Sorteer de volgende elementen. Kies als pivot steeds het meest linker element. Schrijf alle stappen uit!

4 8 2 9 1 5

Slide 11 - Tekstslide

Antwoord oefenvraag 1
Sorteer de volgende elementen. Kies als pivot steeds het meest linker element. Schrijf alle stappen uit!

4 8 2 9 1 5

Slide 12 - Tekstslide

Oefenvraag 2
Sorteer de volgende elementen. Kies als pivot steeds het meest linker element. Schrijf alle stappen uit!

1  9  7  9  1  7

Slide 13 - Tekstslide

Antwoord oefenvraag 2
Sorteer de volgende elementen. Kies als pivot steeds het meest linker element. Schrijf alle stappen uit!

1  9  7  9  1  7

Slide 14 - Tekstslide

Keuze van de pivot
Tot nu toe hebben we steeds als pivot het meest linker element gekozen. De pivot mag echter willekeurig gekozen worden.

Het algoritme werkt dus ook als je bijvoorbeeld steeds het middelste element van de lijst kiest of het meest rechter element.

Slide 15 - Tekstslide

Oefenen met pivot
Sorteer de lijsten 7 6 5 4 3 2 1 en 2 3 5 7 6 4 1 twee keer met QuickSort

Kies de eerste keer steeds het meest linker element als pivot. 

Kies de tweede keer steeds het middelste element als pivot. Als er geen middelste is, kies dan het eerste element rechts van het midden als pivot. 
timer
10:00

Slide 16 - Tekstslide