Sorteren 2: mergesort en quicksort

Een miljoen waarden sorteren door elk paar te vergelijken kost ongeveer 500 miljard vergelijkingen; mergesort heeft er ongeveer 20 miljoen nodig.

Splits het probleem en los de helften op

De methoden uit het vorige hoofdstuk werken op de hele lijst tegelijk en betalen daarvoor ongeveer n² vergelijkingen. De twee methoden hier gebruiken een ander plan, verdeel en heers. Splits de lijst in kleinere delen, sorteer elk deel met dezelfde methode en combineer de gesorteerde delen. Het splitsen gaat door tot een deel één waarde of geen heeft; een lijst van één waarde is al gesorteerd. Omdat de methode zichzelf aanroept op kleinere lijsten, is zij recursief (in hoofdstuk 6 bekijk je recursie in detail).

Mergesort: het werk zit in het samenvoegen

Mergesort deelt de lijst doormidden, sorteert de linkerhelft, sorteert de rechterhelft en voegt beide gesorteerde helften samen. Het slimme deel is het samenvoegen. Twee gesorteerde lijsten kun je combineren door alleen hun voorste waarden te bekijken. Vergelijk die, schrijf de kleinste op en schuif daar voorbij. Herhaal tot één lijst leeg is en kopieer dan de rest van de andere. [1, 4, 7] en [2, 3, 8] samenvoegen gaat als 1 (1 tegenover 2), 2 (4 tegenover 2), 3 (4 tegenover 3), 4 (4 tegenover 8), 7 (7 tegenover 8), waarna 8 wordt gekopieerd: 5 vergelijkingen voor 6 waarden. Twee lijsten met samen n waarden samenvoegen kost nooit meer dan n − 1 vergelijkingen.

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // already sorted
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

Waarom is dit snel? Stel je het halveren voor als niveaus. Een lijst van 8 waarden splitst in 2 lijsten van 4, dan 4 lijsten van 2 en dan 8 lijsten van 1: drie niveaus, want 8 kan 3 keer worden gehalveerd. Op elk niveau raken alle samenvoegingen samen elke waarde eenmaal, dus een niveau kost hoogstens ongeveer n vergelijkingen. Met log₂ n niveaus is het totaal ongeveer n log₂ n. Voor een miljoen waarden zijn dat ongeveer 20 miljoen vergelijkingen, tegenover ongeveer 500 miljard voor de methoden die elk paar vergelijken. Gesplitst als [38, 27, 43, 3] en [9, 82, 10], zoals in het lab, kost [38, 27, 43, 3, 9, 82, 10] 14 vergelijkingen; de code hierboven splitst in 3 en 4 en kost 13.

De prijs is geheugen. Samenvoegen vraagt een plek om de uitvoer te schrijven, dus mergesort gebruikt een tweede lijst zo groot als de invoer. Mergesort is ook stabiel: waarden die gelijk vergelijken behouden hun oorspronkelijke volgorde, omdat bij gelijke voorste waarden de linker wordt genomen. Dat is belangrijk als je een tabel achtereenvolgens op verschillende kolommen sorteert, bijvoorbeeld op stad en dan op naam.

Quicksort: splits rond een spil

Quicksort verdeelt de lijst anders. Het kiest één waarde, de spil, en herschikt de lijst zodat alles kleiner dan de spil ervoor komt en de rest erna. Deze stap heet partitioneren. De spil staat nu definitief goed en beide kanten kun je afzonderlijk met dezelfde methode sorteren. Achteraf samenvoegen is niet nodig, omdat elke waarde links al kleiner is dan elke waarde rechts.

In het lab gebruik je een gangbare leerboekversie die de laatste waarde van elk deel als spil neemt. Op [5, 1, 4, 2, 8] wordt spil 8 met de vier andere, kleinere waarden vergeleken, dus 8 blijft achteraan. Het volgende deel [5, 1, 4, 2] gebruikt spil 2: alleen 1 is kleiner, dus na twee verwisselingen is de lijst [1, 2, 4, 5, 8]. Nog één vergelijking verwerkt [4, 5]. Totaal: 8 vergelijkingen en 2 verwisselingen.

Als de spil dicht bij het midden uitkomt, halveert elke splitsing het probleem en kost quicksort ongeveer n log₂ n vergelijkingen, net als mergesort. Het werkt ook binnen de oorspronkelijke lijst zonder tweede kopie. Maar een slechte spil schaadt. Als de lijst al gesorteerd is en de spil altijd de laatste waarde, haalt elke splitsing slechts één waarde weg en valt quicksort terug op ongeveer n²/2 vergelijkingen: 10 voor [1, 2, 3, 4, 5], hetzelfde als selectionsort. Echte bibliotheken vermijden dit door de spil zorgvuldiger te kiezen, bijvoorbeeld willekeurig of als middelste van drie steekproefwaarden.