Les 5 - QuickSort

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

QuickSort

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.

Links Bubblesort, begin, rechts Quick sort, helemaal

Opdracht:

Neem een stapeltje kaarten en sorteer het volgens

1. BubbleSort
2. Quicksort

Daarna maak je een random rij, met het programma Boomstructuurmaken.fprg en sorteer je die met Bubblesort (5 getallen) en dezelfde rij met Quicksort.

Schrijf het uit, maak een foto en upload die

Neem een stapeltje kaarten en sorteer het volgens QuickSort

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.

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.

Voorbeeld

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

5  3  8  2  7  1

Antwoord

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

5  3  8  2  7  1

Oefenvraag 1

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

4 8 2 9 1 5

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

Oefenvraag 2

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

1  9  7  9  1  7

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

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.

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.