Algoritme Les 4

1 / 27
next
Slide 1: Slide
InformaticaMiddelbare schoolhavo, vwoLeerjaar 4

This lesson contains 27 slides, with interactive quiz and text slides.

time-iconLesson duration is: 50 min

Items in this lesson

Slide 1 - Slide

vandaag
  • Herhaling
  • Insertion Sort Algoritme
  • Heap Sort Algoritme

Slide 2 - Slide

Soorten Algoritmen
  • Selection Sort
  • Bubble Sort
  • Insertion Sort
  • Quick Sort
  • Merge Sort
  • Heap Sort

Slide 3 - Slide

Hoe sorteer jij je kaarten in je hand als je gaat kaarten?

Slide 4 - Open question

Insertion Sort
Insertion sort wordt ook wel card sort genoemd en met reden. De manier van sorteren laat zich het meest vergelijken met het sorteren van stapeltje kaarten aan het begin van een kaartspelletje. Je pakt dan een kaart en steekt hem op de juiste plek tussen de andere kaarten.

Slide 5 - Slide

Insertion Sort
  1. Pak een element uit de lijst ongesorteerde elementen.
  2. Pak een nieuw element uit de lijst
  3. Vergelijk dit met het laatste element uit de gesorteerde lijst. Is het groter, dan voeg je het na het te vergelijken element in en ga verder met stap 2, is het kleiner, dan ga je naar stap 4.
  4. Schuif een plek op naar links en ga verder naar stap 3

Slide 6 - Slide

de ongesorteerde rij

Slide 7 - Slide

Stap 1

Slide 8 - Slide

Stap 2

Slide 9 - Slide

Stap 3

Slide 10 - Slide

Stap 4

Slide 11 - Slide

Slide 12 - Slide

Heap Sort

Een snelle manier van sorteren is heap sort.
Heap sort is in de meeste gevallen langzamer dan quick sort, maar efficiënter in geheugengebruik.

Slide 13 - Slide

Heap sort stopt alle elementen in een binaire boom. Vervolgens wordt de boom dusdanig geordend dat altijd de ouder een hoger element is dan zijn kinderen. Dit betekent dat de wortel van de boom uiteindelijk het hoogste element bevat. Dit element wordt uit de boom de verwijderd en vervangen voor het onderste, meest rechtse element (het laatste kind). .

Slide 14 - Slide

Na deze stap is de boom niet meer geordend, en moet de boom eerst opnieuw geordend worden. Zodra dat proces klaar is, staat opnieuw het hoogste element uit de boom bovenaan. Ook dit element wordt uit de boom verwijderd en achter het vorige hoge element in een aparte lijst gezet. Dit proces herhaalt zich tot de boom uiteindelijk leeg is

Slide 15 - Slide

Slide 16 - Slide

Slide 17 - Slide

1,12,9,5,6,10
Maak een boom structuur waar elk element twee kinderen krijgt. Zo nodig krijgen ook deze twee kinderen elk weer twee kinderen. Deze boomstructuur dient zo gebalanceerd mogelijk te zijn.

Slide 18 - Slide

1,12,9,5,6,10
  • Begin onderaan rechts.
  • Vergelijk de kinderen met de ouder.
  • Als het kind niet het laagste element is, verwissel dan de ouder met het hoogste kind

Slide 19 - Slide

  • Als er links nog een ouder-kind stel is, schuif dan door naar links en herhaal de vorige stap Zo niet, ga dan een regel hoger rechts en herhaal de vorige stap.

Slide 20 - Slide

  • Als er geen hogere regel is ga dan naar de volgende stap
  • De boom is niet meer geordend, controleer het ouder-kinderen stel dat net veranderd is. Als het ouder niet het hoogste element is, verwissel de ouder met het hoogste element van de kinderen. In dit geval herhaal deze stap voor het veranderde kind (beschouw dit kind nu als de ouder).

Slide 21 - Slide

Als er geen kinderen meer zijn, dan is de boom weer geordend ga nu verder met stap van een geordende boom.

Slide 22 - Slide

Slide 23 - Link

Enkele opmerkingen over sorteren
  • Sorteren op de computer kan op verschillende manieren.
  • Wat opvalt, is dat met name de grotere groepen laten zien dat sommige algoritmen niet altijd even geschikt zijn. Kleinere groepen hebben echter ook vaak problemen.
  • Zo hebben quick sort, merge sort en vooral heap sort relatief veel voorwerk nodig als de te sorteren groep maar klein is. Een enkel keertje valt dat nog te overzien, maar als de computer veel kleine groepen in korte tijd moet sorteren dan telt het wel op.


Slide 24 - Slide

  • Over het algemeen wordt in de praktijk quick sort en merge sort, dan wel variaties op deze algoritmen het meest gebruikt.
  • Select sort, bubble sort en ook wel insertion sort worden vooral nuttig gevonden als voorbeelden van computer algoritmen, maar niet efficiënt genoeg om daadwerkelijk in de praktijk te gebruiken.
  • Heap sort wordt vooral gebruikt als er weinig geheugen ruimte is voor het sorteren.
  • Het algoritme is redelijk snel maar wordt vertraagd door het voorwerk.

Slide 25 - Slide

  • Op internet is er veel uitleg en zijn er veel animaties te vinden over de verschillende sorteer algoritmen.

Slide 26 - Slide

Volgende les:
  • Eindige Automaten
  • Oefenen

Slide 27 - Slide