Sorteeralgoritme: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
k r2.6.4) (Robot: toegevoegd: kk:Мәліметтерді сұрыптау |
|||
Regel 15:
== Algoritmen ==
* ''[[
* ''[[Bubblesort]]'': *'' [[Counting sort]]
* [[Insertion sort]]▼
* ''[[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.▼
* [[Selection 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.▼
* [[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<sup>2</sup>), 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 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.
{| style="float:right;"
|[[Bestand:Odd even sort animation.gif|right|Odd even sort]]
Regel 30 ⟶ 25:
|Odd even sort
|}
* ''[[
▲* ''[[Insertion sort]]''
▲* [[Counting sort]] is een efficiënt sorteeralgoritme, dat alleen geschikt is voor gehele getallen in een beperkt bereik.
▲* ''[[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]]''
▲* ''[[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<sup>2</sup>), 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.
| |||