Sorteeralgoritme

Een sorteeralgoritme is een algoritme om elementen van een lijst in een bepaalde volgorde te zetten. In de geschiedenis van het programmeren zijn vele algoritmen voor deze taak bedacht die zich onderscheiden door verschillende snelheid, geheugengebruik en gedrag bij toename van het aantal te sorteren elementen. Het sorteren van bijvoorbeeld een pak speelkaarten stelt andere eisen dan het sorteren van het telefoonboek van New York.

Het bestuderen van sorteeralgoritmen is in veel informaticaopleidingen een manier om veel aspecten van het gebruik van computers uit te leggen. Sorteeralgoritmen vinden ook toepassing bij datacompressie.

Donald Knuth heeft in zijn klassieke werk The art of computer programming een belangrijk deel aan sorteer- en zoekalgoritmen gewijd^[1].

[bewerk] Eigenschappen

Eigenschappen waarin sorteeralgoritmen verschillen zijn o.a.:

eenvoud van de methode;
snelheid van de methode en de mate waarin deze afneemt als het sorteerprobleem groter wordt (meer te sorteren elementen);
geheugengebruik;
gebruik van niet-willekeurig leesbaar perifeer geheugen (b.v. tapes of schijven)
pathologische gevallen (worst case) waarbij het algoritme zich ineens veel slechter dan normaal gedraagt (bijvoorbeeld als de lijst al gesorteerd is, of als de lijst precies in omgekeerde volgorde is gesorteerd);
stabiliteit, het op volgorde houden van elementen die gelijk zijn.

[bewerk] Algoritmen

Bekende algoritmen zijn o.a.:

Bubblesort. De complexiteitsgraad van bubblesort is n², daardoor is het voor lange lijsten bijzonder inefficiënt, behalve als de elementen toevallig al bijna op volgorde liggen. Bubblesort is erg eenvoudig te begrijpen.
Insertion sort
Shellsort
Straight selection sort
Mergesort werkt door het afwerken van verschillende lijsten op volgorde, en is daardoor bijzonder geschikt als de hoeveelheid te sorteren gegevens veel groter is dan in het computergeheugen kan worden opgeslagen (vroeger werd dan met tapes gewerkt, die nooit volledig in het geheugen pasten). De methode is bovendien (mits correct geschreven) stabiel.
Heapsort
Quicksort. De complexiteitsgraad van quicksort is n log n. Dit is in veel gevallen voor grote lijsten de efficiëntste bekende methode. De methode is eenvoudig uit te leggen, maar het is niet meteen intuïtief duidelijk waarom hij zo goed werkt. Verder heeft hij een zeer slechte worst case (n²), wat echter door een kleine ingreep (b.v. willekeurige selectie van het kantelpunt) eenvoudig te ondervangen is. In normale situaties komt deze worst case ook niet voor.
Hashsort. De complexiteitsgraad van hashsort is n. Dit maakt hashsort tot het snelst mogelijke sorteeralgoritme. Het geheugengebruik is echter niet altijd gunstig en bovendien werkt het slecht voor lijsten die uit veel dezelfde items bestaan. Verder is het niet zeker dat de resterende gesorteerde volgorde geen lege elementen bevat, en moet er een manier worden gevonden om elementen die tot dezelfde hashkey leiden, te onderscheiden.
Counting sort is een efficiënt sorteeralgoritme, dat alleen geschikt is voor gehele getallen in een beperkt bereik.
Bogosort is voor de grap voorgesteld als het theoretisch slechtste sorteeralgoritme.

Veel sorteerroutines die in programmeerbibliotheken voorkomen bestaan uit een aantal algoritmen die daar worden ingezet waar ze sterk zijn. Zo kan bijvoorbeeld quicksort voor lange lijsten goed worden gecombineerd met straight selection sort voor korte lijsten.

[bewerk] referenties

↑ Donald E. Knuth, The art of computer programming, volume 3: Sorting and searching. Second edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0