Sorteeralgoritmes uitgelegd: van insertion sort tot quicksort

Sorteren is het bekendste probleem uit de informatica: zet een rij getallen van klein naar groot. Je gebruikt in de praktijk bijna altijd de ingebouwde sort(), maar op het tentamen moet je laten zien dat je snapt wat er onder de motorkap gebeurt. De klassieke vraag is: "hoe ziet de array eruit na ronde 2?" En in sollicitatiegesprekken is "waarom is quicksort in het slechtste geval kwadratisch?" een vaste kandidaat.

Op deze pagina behandelen we vijf algoritmes. Bij elk staat een uitgewerkt voorbeeld met de toestand na elke ronde, precies zoals de oefeningen eronder het vragen. Ken je Big-O nog niet goed, lees dan eerst complexiteit.

Wat betekent "na ronde k"?

Een traceervraag heeft alleen één goed antwoord als iedereen dezelfde variant bedoelt. Op Practicely gelden deze afspraken (rondes tellen vanaf 1, arrays zijn 0-geïndexeerd):

In alle voorbeelden hieronder sorteren we dezelfde array: [5, 2, 4, 6, 1, 3].

Insertion sort

Insertion sort (invoegend sorteren) werkt zoals je kaarten in je hand sorteert: je pakt de volgende kaart en schuift hem naar links tot hij op zijn plek zit. Het deel links van de huidige positie is steeds al gesorteerd.

Let op ronde 3: 6 is groter dan alles links ervan, dus er verandert niets. Dat telt wél als ronde.

def insertion_sort(a):
    for k in range(1, len(a)):
        x = a[k]
        j = k - 1
        # schuif grotere elementen één plek naar rechts
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x  # na ronde k is a[0..k] gesorteerd

static void insertionSort(int[] a) {
    for (int k = 1; k < a.length; k++) {
        int x = a[k];
        int j = k - 1;
        // schuif grotere elementen één plek naar rechts
        while (j >= 0 && a[j] > x) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x; // na ronde k is a[0..k] gesorteerd
    }
}

Omdat de while stopt zodra a[j] > x niet meer geldt, schuiven gelijke elementen nooit langs elkaar. Daardoor is insertion sort stabiel. Op een al gesorteerde array doet de binnenlus niets: dan is het O(n).

Selection sort

Selection sort (selecterend sorteren) zoekt in elke ronde het kleinste element van het ongesorteerde deel en wisselt het naar voren.

In ronde 2 staat het minimum al op zijn plek; de "wissel" van a[1] met zichzelf verandert niets. In ronde 1 zie je ook waarom selection sort niet stabiel is: de 5 springt in één keer van voren naar index 4, over andere elementen heen. Bij gelijke waarden kan zo'n sprong hun volgorde omdraaien: [3a, 3b, 1] wordt na ronde 1 [1, 3b, 3a].

def selection_sort(a):
    n = len(a)
    for k in range(1, n):
        # zoek het minimum in a[k-1..n-1]
        m = k - 1
        for j in range(k, n):
            if a[j] < a[m]:
                m = j
        # wissel altijd, ook als m == k-1
        a[k - 1], a[m] = a[m], a[k - 1]

static void selectionSort(int[] a) {
    int n = a.length;
    for (int k = 1; k < n; k++) {
        // zoek het minimum in a[k-1..n-1]
        int m = k - 1;
        for (int j = k; j < n; j++) {
            if (a[j] < a[m]) {
                m = j;
            }
        }
        // wissel altijd, ook als m == k-1
        int tmp = a[k - 1];
        a[k - 1] = a[m];
        a[m] = tmp;
    }
}

Selection sort doet altijd evenveel vergelijkingen, ongeacht de invoer: n(n-1)/2. Ook een al gesorteerde array kost dus O(n²).

Bubble sort

Bubble sort loopt van links naar rechts en wisselt twee buren als de linker groter is. Het grootste element "borrelt" zo in één doorloop naar het einde.

Ronde 1 in detail: 5>2 wissel, 5>4 wissel, 5<6 niets, 6>1 wissel, 6>3 wissel. Na ronde 1 staat 6 achteraan, na ronde 2 staan 5, 6 achteraan, enzovoort.

Na ronde 4 is de array al gesorteerd. Er bestaat een variant die dan stopt (als een ronde geen enkele wissel deed), maar volgens onze afspraak loopt bubble sort altijd alle n-1 rondes door.

def bubble_sort(a):
    n = len(a)
    for r in range(1, n):
        # na ronde r staan de r grootste achteraan, die slaan we over
        for j in range(n - r):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

static void bubbleSort(int[] a) {
    int n = a.length;
    for (int r = 1; r < n; r++) {
        // na ronde r staan de r grootste achteraan, die slaan we over
        for (int j = 0; j < n - r; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

Merge sort

Merge sort (samenvoegend sorteren) is verdeel-en-heers (divide and conquer): splits de array in twee helften, sorteer elke helft recursief en voeg de twee gesorteerde helften samen. We splitsen in a[0..mid-1] en a[mid..n-1] met mid = ⌊n/2⌋.

Bij het samenvoegen vergelijk je steeds de voorste elementen van beide helften en pak je de kleinste. Bij gelijke waarden pak je eerst links: daardoor is merge sort stabiel.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    links = merge_sort(a[:mid])
    rechts = merge_sort(a[mid:])
    # samenvoegen: bij gelijke waarden eerst links (stabiel)
    res = []
    i = j = 0
    while i < len(links) and j < len(rechts):
        if links[i] <= rechts[j]:
            res.append(links[i])
            i += 1
        else:
            res.append(rechts[j])
            j += 1
    res.extend(links[i:])
    res.extend(rechts[j:])
    return res

static int[] mergeSort(int[] a) {
    if (a.length <= 1) {
        return a;
    }
    int mid = a.length / 2;
    int[] links = mergeSort(java.util.Arrays.copyOfRange(a, 0, mid));
    int[] rechts = mergeSort(java.util.Arrays.copyOfRange(a, mid, a.length));
    // samenvoegen: bij gelijke waarden eerst links (stabiel)
    int[] res = new int[a.length];
    int i = 0, j = 0, k = 0;
    while (i < links.length && j < rechts.length) {
        if (links[i] <= rechts[j]) {
            res[k++] = links[i++];
        } else {
            res[k++] = rechts[j++];
        }
    }
    while (i < links.length) res[k++] = links[i++];
    while (j < rechts.length) res[k++] = rechts[j++];
    return res;
}

Er zijn log n niveaus van splitsen, en op elk niveau kost samenvoegen samen O(n). Totaal: O(n log n), altijd. Het nadeel: je hebt een extra array van grootte n nodig.

Quicksort met Lomuto-partitie

Quicksort kiest een spil (pivot), zet alles wat kleiner is links ervan en de rest rechts, en sorteert daarna beide kanten recursief. Het hart is de partitie. Wij gebruiken de Lomuto-partitie met het laatste element als pivot:

pivot = a[hi]; i = lo
for j = lo .. hi-1:
    if a[j] < pivot: swap(a[i], a[j]); i++
swap(a[i], a[hi]); return i

i wijst naar de eerste plek waar het volgende "kleine" element moet komen. Elementen die strikt kleiner zijn dan de pivot gaan naar links; gelijke elementen blijven rechts.

Uitgewerkt op [7, 2, 9, 4, 1, 8, 5], pivot = 5:

Na de eerste partitie is de array 2, 4, 1, 5, 9, 8, 7 en staat de pivot 5 op index 3, zijn definitieve plek. Links staan alleen kleinere getallen, rechts alleen grotere, maar beide kanten zijn nog niet gesorteerd. Quicksort gaat nu verder met a[0..2] en a[4..6].

def partition(a, lo, hi):
    pivot = a[hi]  # laatste element is de pivot
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:  # strikt kleiner gaat naar links
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]  # pivot op zijn definitieve plek
    return i

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = partition(a, lo, hi)
        quicksort(a, lo, p - 1)
        quicksort(a, p + 1, hi)

static int partition(int[] a, int lo, int hi) {
    int pivot = a[hi]; // laatste element is de pivot
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) { // strikt kleiner gaat naar links
            int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++;
        }
    }
    int tmp = a[i]; a[i] = a[hi]; a[hi] = tmp; // pivot op zijn definitieve plek
    return i;
}

static void quicksort(int[] a, int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quicksort(a, lo, p - 1);
        quicksort(a, p + 1, hi);
    }
}

Valt de pivot steeds ongeveer in het midden, dan halveer je het probleem en kom je op O(n log n). Maar is de array al gesorteerd, dan is het laatste element steeds het grootste. De partitie levert dan een linkerdeel van n-1 elementen en een leeg rechterdeel op. Dat geeft T(n) = T(n-1) + n, en dus O(n²). In de praktijk kies je daarom vaak een willekeurige pivot.

Stabiel en in-place

Twee eigenschappen die op het tentamen vaak gevraagd worden:

• Stabiel (stable): gelijke elementen behouden hun onderlinge volgorde. Belangrijk als je eerst op naam en daarna op leeftijd sorteert: binnen dezelfde leeftijd blijft de naamvolgorde dan staan.
• In-place: het algoritme gebruikt maar O(1) (of hooguit O(log n)) extra geheugen naast de array zelf.

Complexiteit

Bubble sort met vroegtijdige stop heeft een best case van O(n); zonder stop, zoals wij hem definiëren, is ook de best case O(n²). Het geheugen van quicksort is de recursiestapel: gemiddeld O(log n), in het slechtste geval O(n).

Veelgemaakte fouten op het tentamen

1. Insertion en selection sort verwisselen. Insertion sort pakt het volgende element en schuift het op zijn plek; het gesorteerde deel bevat dan nog niet per se de kleinste. Selection sort zoekt het kleinste in de rest. Na ronde 1 van 5, 2, 4, 6, 1, 3 geeft insertion 2, 5, 4, 6, 1, 3, selection 1, 2, 4, 6, 5, 3.
2. Een ronde overslaan omdat er niets verandert. Bij insertion sort telt ronde 3 hierboven gewoon mee, ook al blijft de array gelijk.
3. Bubble sort vroegtijdig stoppen. Volgens de afspraak loop je alle n-1 rondes door. Bij een vraag als "hoeveel vergelijkingen?" maakt dat uit.
4. De laatste wissel van Lomuto vergeten. Na de lus staat de pivot nog achteraan; pas de swap(a[i], a[hi]) zet hem op index i. Ook: gelijke waarden aan de pivot gaan niet naar links, alleen strikt kleinere.
5. Denken dat quicksort altijd O(n log n) is. Met het laatste element als pivot is een gesorteerde invoer het slechtste geval: O(n²).

Samenvatting

• Insertion sort: na ronde k is a[0..k] gesorteerd; snel op bijna gesorteerde data, stabiel.
• Selection sort: na ronde k staan de k kleinsten vooraan; altijd O(n²), niet stabiel.
• Bubble sort: na ronde k staan de k grootsten achteraan; O(n²), stabiel.
• Merge sort: altijd O(n log n) en stabiel, maar kost O(n) extra geheugen.
• Quicksort (Lomuto, laatste element als pivot): gemiddeld O(n log n) en in-place, slechtst O(n²).