Sorteeralgoritmen

Sorteeralgortimen staan aan de basis van de informatica. Welke methodes kun je allemaal bedenken waarop je lijsten kunt sorteren? In je profielwerkstuk kun je bijvoorbeeld een eigen sorteeralgoritme programmeren en analyseren uittesten.

Er is bijna geen enkel computerprogramma dat zou werken zonder een vorm van sorteren in de achtergrond. Er zijn allerlei verschillende manieren om een lijst te sorteren. Neem bijvoorbeeld een boekenkast die je wilt sorteren op achternaam van de auteur.

Één methode is om op zoek te gaan naar de auteur met een achternaam die start met een A, daarna de B, enzovoorts. Een andere methode is om te starten met een willekeurig boek, een volgend boek te pakken, en die op de juiste plek te zetten, ofwel ervoor of erachter. Je kunt ook alle boeken door elkaar op de grond gooien, ze oprapen, en kijken of ze op volgorde staan (en zo niet, het nog eens proberen). Welke methode is efficiënter?

Stel nu, je bent met z’n tweeën. Hoe pak je het dan aan? Verdelen jullie de stapels in tweeën? Of werk je tegelijkertijd aan dezelfde stapel (en wat doe je als dat niet kan)? Hoe kun je de werklast het best verdelen?

Kun je voorspellen hoe vaak je gemiddeld een boek moet oppakken en bekijken, voordat de hele lijst gesorteerd is? Of hoe vaak je een boek moet verplaatsen? Maakt het uit of je veel auteurs hebt met een letter A en weinig met een Z (of andersom), of is een methode altijd efficient ongeacht hoe ‘de data’ eruit ziet?

Dit zijn allemaal vragen die je kunt beantwoorden voor verschillende sorteeralgoritmen.

Interessante vragen

  • Welke methodes kun je allemaal bedenken waarop je lijsten kunt sorteren?
  • Hoe efficient zijn die en onder welke voorwaarden?
  • Kun je een eigen sorteeralgoritme programmeren en analyseren of uittesten?

Literatuurtips