Programmeren met spreadsheets/Voorbeeld: zoeken en sorteren

Uit Lab
Naar navigatie springen Naar zoeken springen
De printervriendelijke versie wordt niet langer ondersteund en kan weergavefouten bevatten. Werk uw browserbladwijzers bij en gebruik de gewone afdrukfunctie van de browser.

Zoeken: raad een getal

Zoekproblemen kom je in de informatica erg veel tegen. In sommige gevallen kun je niets slimmers vinden dan het stuk-voor-stuk onderzoeken van alle mogelijke waarden. We spreken in dit geval over lineair zoeken (Linear Search): het aantal elementen dat je moet onderzoeken voordat je de gezochte waarde hebt is evenredig met het totale aantal elementen.

Als je een alfabetische lijst met namen en bijbehorende telefoonnummers hebt, en je wilt een naam zoeken bij een gegeven telefoonnummer, dan moet je alle elementen van de lijst stuk voor stuk onderzoeken.

Als de elementen op een bepaalde manier georganiseerd zijn kun je vaak slimmer zoeken. We kunnen in een woordenboek snel zoeken door gebruik te maken van de alfabetische volgorde. Dit is ook de belangrijkste reden voor het sorteren van een lijst: je kunt in het resultaat sneller zoeken.

Sorteren

Zoals gezegd is sorteren belangrijk. We geven hier een voorbeeld van een sorteeralgoritme. Dit is niet de meest handige manier van sorteren: het aantal vergelijkingen dat we moeten doen is evenredig met het kwadraat van de lengte van de rij. (Ga dit na.) We spreken dan wel over een kwadratisch algoritme. Maar de resulterende spreadsheet maakt het sorteerproces wel erg inzichtelijk.