Sorteeralgoritmes

Een sorteeralgoritme is een stuk programmacode om een reeks getallen van klein naar groot te sorteren. Neem bijvoorbeeld deze reeks willekeurige getallen:

Het is de bedoeling dat die getallen netjes gesorteerd worden, van klein naar groot. Het resultaat wordt dus:

Er zijn een heleboel verschillende manieren om een computer dat voor elkaar te laten krijgen. Die manieren heten sorteeralgoritmes

Ieder algoritme heeft voordelen, maar ook nadelen. Er is (nog) geen perfect algoritme, dat altijd het beste is. Je moet dus een algoritme kiezen. Welk algoritme je kiest, is afhankelijk waar je het voor wilt gebruiken. Om het telefoonboek van New York te sorteren, gebruik je een ander sorteeralgoritme dan om een lijstje van 10 nummers te sorteren. Dat komt omdat het telefoonboek heel groot is, en veel gegevens bevat. Een sorteeralgoritme om een telefoonboek te sorteren, moet dus heel snel zijn. Zo heeft ieder algoritme een aantal eigenschappen:

• Stabiliteit
• Average Case, Worst Case en Best Case
• Eenvoud / complexiteit van het algoritme
• Snelheid voor verschillende aantallen van te sorteren elementen
• Geheugengebruik

En zo zijn er nog een aantal minder belangrijke eigenschappen.

Stabieliteit

Een sorteeralgoritme is stabiel als hij elementen met dezelfde waarden niet door elkaar gooit (de volgorde niet veranderd).
Voorbeeld: Stel dat je een quiz hebt, waarbij de 3 mensen die het minste fout hebben een prijs krijgen. Als er mensen zijn die evenveel fout hebben, krijgt de persoon die het eerste heeft ingezonden de prijs.
Allereerst stuurt Jan zijn antwoorden in. Hij heeft er 24 fout.
Daarna stuurt Piet zijn antwoorden in. Hij heeft er 19 fout.
Na Piet heeft Mark ook de quiz af. Hij heeft er 20 fout.
Dan krijgen we de antwoorden van Tim, hij heeft er 15 fout.
Als laatst stuurt Joost zijn antwoorden in, hij heeft er ook 20 fout.
We krijgen dan dus de volgende tabel:

Naam:	Fouten:
Jan	24
Piet	19
Mark	20
Tim	15
Joost	20

Hier krijgt Tim de eerste prijs, omdat hij het minste fout heeft. De tweede prijs krijgt Piet, en de derde prijs krijgt Mark. Hoewel Joost evenveel fout heeft als Mark, krijgt hij geen prijs omdat hij later dan Mark heeft ingezonden.
In dit voorbeeld was het belangrijk dat er een stabiel sorteeralgoritme werd gekozen, want anders zou hij de volgorde tussen Mark en Joost kunnen veranderen, waardoor Joost een prijs krijgt in plaats van Mark.

Een algoritme is dus niet stabiel als hij een lijst altijd volledig sorteerd, zoals vaak gedacht wordt.

Average Case, Worst Case en Best Case

Average Case is de tijd die het algoritme gemiddeld nodig heeft, geschreven in de complexiteitsgraad, afhankelijk van het aantal te sorteren elementen n. Het ideale Average Case is O(n). Veel goede sorteeralgorimes hebben als Average Case O(n log n).

Worst Case is de tijd die het algoritme nodig heeft in het slechtste geval. Bij sommige algoritmes is het slechtste geval als de lijst bijvoorbeeld precies omgekeerd gesorteerd is, of juist als hij al helemaal goed gesorteerd is. Veel algoritmes hebben als Worst Case O(n²).

Best Case is de tijd die het algoritme nodig heeft in het beste geval, bijvoorbeeld als de lijst al helemaal goed gesorteerd is. Vaak is de Best Case O(n).

Eenvoud / complexiteit

Sommige algoritmes zijn heel eenvoudig te begrijpen, terwijl andere algoritmes erg moeilijk te begrijpen zijn. Zulke algoritmes moet je eerst goed bestuderen voor je ze goed snapt.

Snelheid

Sommige algoritmes zijn erg snel, terwijl andere erg traag zijn. Bij alle algoritmes is de snelheid afhankelijk van het aantal te sorteren elementen. Zie ook de Average Case, Worst Case en Best Case.

Geheugengebruik

Geheugengebruik kan ook een rol spelen bij het kiezen van sorteeralgoritmes. Zo gebruiken recursieve algoritmes vaak meer geheugen dan niet-recursieve. Bij gigantisch grote lijsten groter dan het geheugen is een algoritme dat weining geheugen gebruikt noodzakelijk.

Overzicht van algoritmes

Hier is een overzicht van veel gebruikelijke sorteeralgoritmes, met hun eigenschappen:

Naam	Average Case	Worst Case	Geheugengebruik	Stabiel	Methode
Selection Sort	O(n2)	O(n2)	O(1)	Nee	Selectie
Bubble Sort	(onbekend)	O(n2)	O(1)	Ja	Verwisselen
Bubble Sort 2	(onbekend)	(onbekend)	(onbekend)	Ja	Verwisselen

---