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 en geheugenbeheer.
Donald Knuth heeft in zijn klassieke werk The art of computer programming een belangrijk deel aan sorteer- en zoekalgoritmen gewijd.[1]
Eigenschappen bewerken
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 dezelfde volgorde houden van elementen die gelijk zijn. Dit is belangrijk als men na elkaar op verschillende kenmerken wil sorteren.
Algoritmen bewerken
Enige algoritmen zijn:
- Bogosort (ook stupid sort of slowsort) is voor de grap voorgesteld als het theoretisch slechtste sorteeralgoritme.
- Bubblesort: de complexiteitsgraad van bubblesort is n2, 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.
- Counting sort: een efficiënt sorteeralgoritme, dat alleen geschikt is voor gehele getallen in een beperkt bereik.
- Hashsort. De complexiteitsgraad van hashsort is n. Dit maakt hashsort tot het snelst mogelijke sorteeralgoritme voor kleine reeksen (voor grote reeksen is een logaritmische complexiteitsgraad sneller (wegens asymptotisch gedrag)). 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.
 |
| Odd even sort |
- Heapsort
- Insertion 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.
- Odd even sort
- Pancake sort
- 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 (n2), 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.
- Radix sort
- Selection sort
- Shellsort
- Straight selection sort
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.
Referenties bewerken
- ↑ 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
Externe links bewerken
- (en) https://web.archive.org/web/20030402131837/http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm Goede uitleg quicksort
- https://web.archive.org/web/20050209143010/http://www.johanstuivenberg.nl/Sorteren/ Verschillende sorteeralgoritmen visueel vergeleken (Java-applet)
