Algoritme Les 4

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

vandaag

• Herhaling
  
• Insertion Sort Algoritme
• Heap Sort Algoritme
  

Soorten Algoritmen

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

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

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.

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

de ongesorteerde rij

Stap 1

Stap 2

Stap 3

Stap 4

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.

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). .

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

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.

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

• 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.
  

• 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).
  

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

https:

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.

• 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.

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

Volgende les:

• Eindige Automaten
• Oefenen