Les 4 - Quicksort

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

Les 4 - 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.

Gegeven de volgende getallenreeks:
1 7 21 3 8 45 0 3 8 9 12 2
Welk sorteer algoritme is hier het handigst?

1. bubblesort
2. mergesort

Sorteer de volgende getallen met bubblesort en toon elke ronde de wisselingen:

9  5  2  1  8  9

Stel dat ik een getal onder de 30 wil laten raden, wat is dan het best case scenario getal?

Sorteer de volgende getallen met de mergesort methode

45 1 3 2 9 8 3 2 12 62 5 33 2 1 2 7

Quicksort maakt net als de mergesort gebruik van de divide-and-conquer methode,

Bekijk het volgende filmpje 2x en schrijf het gevonden algoritme op.

Het algoritme

1. Kies het laatste element in de array als pivot (r)

2. Het eerste element in de array  (p) wordt het startpunt van variabele j. 

3. Variabele i start op  p - 1.

4. Vergelijk a(j) met a(r).  Als a(j) > a(r), doe niets en schuif j een positie naar rechts op. Als a(j) < a(r), dan schuift i een positie naar rechts en verwissel je a(i) en a(j). Schuif a(j) een positie naar rechts op.

5. Als j het eind bereikt, dan moet de pivot (r) op de positie i+1 komen.

Een voorbeeld met getallen: 

Een voorbeeld met getallen: 

4 2 6 1 5 

pivot

4 2 6 1 5 

j

i

j = 4 en r = 5 -> 4 < 5, dus i schuift 1 positie op en i en j verwisselen. Hier is echter i = j.  vervolgens schuift j een plek op.

j = 2 --> 2 < 5, dus i schuift positie op en i en j verwisselen, maar wederom is hier i = j. j schuift positie op. 

j = 6 --> 6 > 5, er gebeurt niets en j schuift positie op. 

j = 1 --> 1 < 5, dus i schuift  positie op en wordt 6. Verwissel i en j. 

j is aan het eind. De pivot komt 1 positie verder dan i, hier tussen de 1 en 6. 

Herhaal voor linker en rechter deel totdat lijst is gesorteerd.

4 2 1 6 5 

4 2 1 5 6  

Soms is het algoritme net iets anders, maar is er nog steeds sprak van een quicksort. Kijk naar het filmpje van de hongaarse dansers die een quicksort uitvoeren. Wat is er anders en waarin is het toch ook weer gelijk? Probeer hier ook de 2e keer het algoritme te achterhalen. Welk getal van welke positie was hier de eerste pivot?

Welk getal van welke positie was hier de eerste pivot?

Welk getal van welke positie was hier de eerste pivot?

1. het getal 3 van positie a[0]
2. het getal 8 van positie a[9]
3. er was hier geen pivot

Schrijf het quicksort algoritme zoals getoond in de dans hier op.

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

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.

Quicksort de volgende rij getallen.  Je mag zelf weten welk van de 3 algoritmes voor quicksort gebruikt, zolang je deze maar correct uitvoert.

4 8 2 9 1 5