13. Gegevens sorteren en zoeken

Het komt regelmatig voor dat je precies dat ene bedrag, die ene naam of dat ene adres uit een hele serie gegevens moet hebben. Als zulke gegevens niet zijn geordend, dan is het zoeken omslachtig en vooral als het om heel veel gegevens gaat. Een manier om gegevens makkelijker toegankelijk te maken, is ze te sorteren. Daarna kun je sneller iets opzoeken. Zoeken gebruik je niet alleen als je iets wilt weten, maar ook als je gegevens wilt verwijderen of tussen voegen. Als gegevens zijn gesorteerd, dan overzie je ze ook makkelijker.

Bubblesort

Bubblesort is de makkelijkste manier om een rij met getallen te sorteren. Bij Bubblesort start aan je het begin van de rij en vergelijk je steeds 2 getallen die naast elkaar liggen, als ze verkeerd om staan dan wissel je ze om, daarna schuif je een positie op. Na eerste ronde staat het laatste getal op de juiste plek. Je gaat door totdat alle getallen op de juiste plek staan. Voorbeeld van Bubblesort zie je hieronder:

Door Swfung8 - CC BY-SA 3.0, via Wikipedia Commons

Opdracht 12.1 Schrijf een programma dat een rij met getallen sorteert met Bubblesort.

Quicksort

Sorteren met het algoritme quicksort gaat een stuk sneller, zoals de naam al doet vermoeden. Bij deze methode worden niet alle elementen afzonderlijk met elkaar vergeleken, maar wordt de rij in steeds in tweeën verdeeld totdat dit niet meer mogelijk is. Het verdelen van de rij in tweeën gebeurd als volgt: - kies een pivot. De pivot kan het eerste getal uit de rij zijn maar ook het laatste of middelste getal. Noem dit getal x. - Zet alle elementen van de rij die kleiner zijn dan x, links van x, en zet alle getallen die groter zijn dan x, rechts van x. Laat daarna dezelfde stappen recursief los op de getallen die links van x staan, en ook op alle getallen die rechts van x staan.

Opdracht 12.2 - Teken op papier een voorbeeld rij getallen en sorteer de getallen met quicksort op papier. - Schrijf een recursief programma dat een rij getallen met de Quick sort methode sorteert.

Opdracht 12.3 In hoofdstuk 10 heb je geleerd over built-in functies. - Is er ook een built-in functie voor het quicksort algoritme? - Welk sorteer algoritme gebruikt de built-in functie sort()?

Binair zoeken

Als je gegevens gesorteerd hebt, dan kun je er een stuk eenvoudiger in zoeken. Natuurlijk kan je als je de naam Haas zoekt beginnen aan het begin van een op alfabet gesorteerde namenlijst en de lijst aflope tot je Haas hebt gevonden. Deze manier van zoeken noemen we lineair zoeken. Je hebt zo weinig profijt van het feit dat de lijst alfabetisch is gesorteerd. Een andere methode is binair zoeken. In hoofdstuk 4 hebben we code geschreven waarbij de computer een random getal kiest en waar jij moest raden wat dit getal is. Na elke gok geeft de computer terug of het getal lager of hoger is dan het antwoord. En zo ga je door totdat je het goede antwoord hebt gevonden. Stel jij kiest nu een getal tussen de 1 en 100 en de computer moet dit getal raden, wat is dan een goede tactiek voor de computer? In dit geval kiest de computer steeds het middelste getal van de nog mogelijke opties. De computer gokt dus eerst het getal 50. Als de computer weet of het getal hoger of lager is dan 50 dan zijn nog maar de helft van de getallen over. De volgende beurt gokt de computer 25 als het getal lager was of 75 als het getal hoger was. Dit verdelen kan de computer voortzetten totdat het getal geraden is. Deze manier van zoeken noemen we binair zoeken.

Opdracht 12.4 Maak de opgave binair zoeken.