# Algoritmen

## Algemene sorteer algoritmen

### Algemeen overzicht


### Mergesort

Verdeel problemen in kleinere deelproblemen die wel makkelijk op te lossen zijn.


**Eigenschappen**
* Stabiel
* O(n log n)
* Gebruikt devide and conquer techniek

**nadeel**
* Hulptable nodig van O(n)
* Sorteert niet ter plaatse
* Je gebruikt beter insertion sort voor kleinere tabellen

### Quick sort

Maakt gebruik van partitionering (Methode van Hoare).

1. Kies een pivot
2. Zolang het element kleiner is dan de pivot blijven verder itereren
3. Als element groter of gelijk aan de pivot is verplaats het element


**Eigenschappen**
* Ter plaatste
* Niet stabiel
* Average case O(nlogn)

**Optimalisaties**
Recursie stoppen bij voldoende kleine deeltabel en sorteren met insertion sort

### Shellsort

Optimalisatie van insertion sort waarbij er wordt gezorgd dat elementen die `h` uit elkaar staan gesorteerd zijn.


**Eigenschappen**
* Niet stabiel
* Ter plaatste
* Tijdscomplexiteit hangt af van de incrementreeks(h)

### Heapsort

Opbouwen van heap als sorteermethode

**Eigenschappen**
* Ter plaatste
* Niet stabiel
* O(nlogn)

**Voordelen**
* Niet recursief
* Geen hulptabellen

## Lineare sorteer methoden

Linear sorteren is in principe niet mogelijk, behalve als we meer weten over de input.

### Countsort

Vereist dat de sleutels gehele getallen zijn en dat ze tot een beperkt interval behoren