Les 4 - Quicksort

Les 4 - Quicksort
1 / 21
next
Slide 1: Slide
InformaticaMiddelbare schoolhavo, vwoLeerjaar 4

This lesson contains 21 slides, with interactive quizzes, text slides and 2 videos.

time-iconLesson duration is: 50 min

Items in this lesson

Les 4 - Quicksort

Slide 1 - Slide

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 - Slide

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

Slide 3 - Quiz


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

9  5  2  1  8  9

Slide 4 - Open question


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

Slide 5 - Open question


Sorteer de volgende getallen met de mergesort methode
45 1 3 2 9 8 3 2 12 62 5 33 2 1 2 7

Slide 6 - Open question

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

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

Slide 7 - Slide

Slide 8 - Video

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.

Slide 9 - Slide

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  

Slide 10 - Slide

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?

Slide 11 - Slide

Slide 12 - Video

Welk getal van welke positie was hier de eerste pivot?
Welk getal van welke positie was hier de eerste pivot?
A
het getal 3 van positie a[0]
B
het getal 8 van positie a[9]
C
er was hier geen pivot

Slide 13 - Quiz


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

Slide 14 - Open question

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 15 - Slide

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

5  3  8  2  7  1

Slide 16 - Slide

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

5  3  8  2  7  1


Slide 17 - Slide

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 18 - Slide

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 19 - Slide

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 20 - Slide


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

Slide 21 - Open question