Algoritmen - quick sort en merge sort

• Informatica
• Middelbare school
• vwo
• Leerjaar 5

Introductie

lgg

Algoritmen

Merge sort

Quick sort

• Je kent enkele standaardalgoritmen en kan deze toepassen in een gegeven context: Merge sort en quick sort

Deze les hoort bij 2.3, 2.5 en 2.6

Bubble sort

https://repl.it/@TimLogtenberg/bubblesort

Sorteer!

4   3   8   1   0   8 

Gebruik bubblesort om deze lijst te sorteren

Bubble sort - aan de slag

Meet het verschil tussen een gesorteerde lijst en een niet gesorteerde lijst. Gebruik als "stopwatch" deze code:

https://repl.it/@TimLogtenberg/stopwatch

niet gesorteerde lijst

list(range(1000))

Tip: bij lijsten groter dan 5000 wordt het een beetje te traag allemaal

Conclusie?

Wat gebeurt hier?

Mergesort

Filmpje

https://fundament-online.nl/student/content.php?paragraaf_id=89930

En nu jij!

4   3   8   1   0   8 

Mergesort is sneller dan Bubblesort

1. Klopt!
2. Klopt not.

Quicksort

Wat gebeurt hier?

Filmpje

https://fundament-online.nl/student/content.php?paragraaf_id=89931

En nu jij!

4   3   8   1   0   8 

Bubble

Quick

Merge

[98,11,2,34,2,14,15,11,34,98,44]

Welk algoritme kan je het beste gebruiken?

1. Quick
2. Bubble
3. Merge

Niet bubble want niet al gesorteerd

Niet quick want dezelfde getallen

Dus merge

Huiswerk (vrijdag)

Bewijs de onderstaande afbeelding. Maak hiervoor een programma in python om dit te meten. Gebruik  als hulpmiddel de code uit de volgende slide.

Sorteer algoritmen - voorbeeld code

• https://repl.it/@TimLogtenberg/bubblesort
• https://repl.it/@TimLogtenberg/mergesort
• https://repl.it/@TimLogtenberg/quicksort

Dit kon er beter aan deze les

Bronnen

• https://www.freecodecamp.org/news/an-intro-to-advanced-sorting-algorithms-merge-quick-radix-sort-in-javascript-b65842194597/

lgg