Samenvatting · Informatica · havo 5 Zoeken en sorteren: lineair en binair zoeken, bubble sort en selection sort

Een algoritme is een stap-voor-stapaanpak die een probleem oplost. Zoeken en sorteren zijn de twee klassiekers: elke telefoon, webwinkel en database doet het de hele dag. Na deze samenvatting voer je zoek- en sorteeralgoritmen met de hand uit en weet je wanneer je welk algoritme kiest.

Wat is een algoritme?

Een algoritme moet eindig zijn (het stopt), eenduidig (elke stap is precies bepaald) en correct (het geeft het goede resultaat). Je beschrijft het in stappen, in pseudocode of in een programmeertaal, en je test het door het met de hand door te lopen.

Lineair zoeken

Bij lineair zoeken loop je de lijst van voor naar achter af en vergelijk je elk element met het gezochte. Je stopt zodra je het vindt. Het werkt op elke lijst, ook een ongesorteerde.

Moet het element er niet in zitten of staat het helemaal achteraan, dan vergelijk je alle $n$ elementen. Bij een lijst van 1000 elementen zijn dat in het slechtste geval 1000 vergelijkingen.

Binair zoeken

Binair zoeken werkt alleen op een gesorteerde lijst, maar is veel sneller. Je kijkt naar het middelste element:

In slechts 2 vergelijkingen is het element gevonden. Elke stap halveert het zoekgebied.

Bubble sort

Bij bubble sort vergelijk je steeds twee naast elkaar liggende elementen en wissel je ze als ze in de verkeerde volgorde staan. Na elke ronde zit het grootste element van het nog ongesorteerde deel op zijn plaats achteraan, als een bel die opstijgt. Je herhaalt tot er in een hele ronde niets meer is gewisseld.

Selection sort

Bij selection sort zoek je in het ongesorteerde deel het kleinste element en wissel je dat met het eerste element van dat deel. Dan schuif je de grens één plaats op.

Vergelijken van algoritmen

Voor lijsten van $n$ elementen:

Bij 1000 elementen heeft lineair zoeken maximaal 1000 stappen nodig, binair zoeken maar zo'n 10, want $2^{10}=1024$. Voor sorteren zijn er veel snellere methoden (zoals quicksort en mergesort), die de lijst telkens in delen splitsen. Bubble sort en selection sort zijn vooral leerzaam en prima voor kleine lijsten.

Wanneer kies je wat?

• Weinig data of ongesorteerd, één keer zoeken: lineair zoeken. Sorteren kost meer dan het zoeken zelf.
• Veel zoekacties op dezelfde data: sorteer één keer en gebruik daarna binair zoeken.
• Heel grote lijsten sorteren: gebruik de sorteerfunctie van de taal, die een snel algoritme gebruikt.

Let op

• Binair zoeken vereist een gesorteerde lijst. Op een ongesorteerde lijst geeft het onbetrouwbare uitkomsten.
• Bubble sort moet doorgaan tot een ronde zonder wissels. Eén ronde is meestal niet genoeg.
• Controleer je algoritme met een kleine lijst en met lastige gevallen: een lege lijst, één element, een element dat er niet in zit, dubbele waarden.

In het kort

• Lineair zoeken werkt overal; binair zoeken vraagt een gesorteerde lijst en halveert het zoekgebied.
• Bubble sort wisselt naburige paren tot er een ronde zonder wissels is.
• Selection sort wisselt het kleinste element naar voren en schuift de grens op.
• Beide sorteermethoden kosten ongeveer $n^2$ stappen; binair zoeken ongeveer ${\log }_{2}n$.
• Test een algoritme met een lege lijst, één element en dubbele waarden.