Sorteren 1: bubblesort, selectionsort en insertionsort

Selectionsort doet precies 45 vergelijkingen op elke lijst van 10 waarden, ongeacht of de lijst door elkaar of al op volgorde begint.

Dingen op volgorde zetten

Sorteren betekent een lijst herschikken zodat de waarden van klein naar groot lopen (of op naam, datum, prijs, elke vergelijkbare volgorde). Het is een van de meest voorkomende computertaken: contacten op een telefoon, zoekresultaten op relevantie, een spreadsheetkolom op datum. Sorteren maakt ook andere taken gemakkelijker. Zoals je in het vorige hoofdstuk zag, kun je een gesorteerde lijst binair doorzoeken en staan dubbele waarden naast elkaar.

In dit hoofdstuk bekijk je drie eenvoudige methoden. Alle drie vergelijken twee waarden tegelijk en verplaatsen waarden binnen dezelfde lijst. Ze zijn kort om te schrijven en gemakkelijk te volgen, maar worden alle drie sterk trager bij lange lijsten. Begrijpen waarom ze vertragen is de beste voorbereiding op de snellere methoden in het volgende hoofdstuk. Steeds tellen we twee dingen: vergelijkingen (vragen ‘is deze waarde groter dan die?’) en verwisselingen (twee waarden omwisselen).

Bubblesort: verwissel buren die verkeerd om staan

Bubblesort loopt langs de lijst en vergelijkt elk paar buren. Is de linker groter, dan worden ze verwisseld. Na één volledige doorgang is de grootste waarde stap voor stap helemaal naar rechts gebracht, zoals een opstijgende luchtbel, en hoeft nooit meer te bewegen. De volgende doorgang kan één plaats eerder stoppen. Een gebruikelijke verbetering is letten op een doorgang zonder verwisselingen: dan staat alles al goed en kan het sorteren vroeg stoppen.

Volg het op [5, 1, 4, 2, 8]. De eerste doorgang vergelijkt 5 en 1 (verwissel), 5 en 4 (verwissel), 5 en 2 (verwissel), 5 en 8 (laat staan): de lijst is nu [1, 4, 2, 5, 8] en 8 staat goed. De tweede doorgang vergelijkt 1 en 4, 4 en 2 (verwissel), 4 en 5 en geeft [1, 2, 4, 5, 8]. De derde vergelijkt 1 en 2, dan 2 en 4, verwisselt niets en stopt. Totaal: 4 + 3 + 2 = 9 vergelijkingen en 4 verwisselingen.

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // swap
        swapped = true;
      }
    }
    if (!swapped) break;  // already sorted
  }
  return a;
}

Selectionsort: vind de kleinste en zet die als volgende

Selectionsort werkt zoals veel mensen speelkaarten sorteren. Doorzoek de hele lijst naar de kleinste waarde en verwissel die naar de eerste positie. Zoek daarna in de rest naar de kleinste overgebleven waarde en verwissel die naar de tweede positie, enzovoort. Op [5, 1, 4, 2, 8] vindt de eerste doorgang 1 en verwisselt die met 5; de tweede vindt 2 en verwisselt die met 5; de laatste twee vinden 4 en 5 al op hun plaats. Dat zijn maar 2 verwisselingen, maar er zijn nog steeds 4 + 3 + 2 + 1 = 10 vergelijkingen.

Selectionsort stopt nooit vroeg. Zelfs bij een al gesorteerde lijst moet het nog elke resterende waarde controleren om zeker te zijn van de kleinste. Voor n waarden tellen de vergelijkingen altijd op tot (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Voor 10 waarden is dat 45; voor 100 waarden 4950; voor 1000 waarden 499 500. De kracht is het kleine aantal verwisselingen: hoogstens n − 1, belangrijk wanneer een waarde verplaatsen duur is.

Insertionsort: schuif elke nieuwe waarde op haar plaats

Insertionsort houdt het linkerdeel gesorteerd en breidt het met één waarde tegelijk uit. Het neemt de volgende waarde en schuift die naar links door met de buur te verwisselen totdat de buur niet groter is. Dan staat die waarde op haar plek tussen de gesorteerde waarden. Bij een lijst die al bijna op volgorde staat, beweegt elke nieuwe waarde maar één of twee stappen, zodat insertionsort daar heel snel is. Op [5, 1, 4, 2, 8] doet het 7 vergelijkingen en 4 verwisselingen.

Verwisselingen tellen: inversies

Er is een handige manier om het aantal verwisselingen van bubblesort en insertionsort te voorspellen. Tel de inversies: paren waarden die onderling verkeerd om staan. In [5, 1, 4, 2, 8] zijn dat (5, 1), (5, 4), (5, 2) en (4, 2), vier in totaal. Elke verwisseling van verkeerd geordende buren herstelt precies één inversie en maakt geen nieuwe, dus beide methoden doen precies 4 verwisselingen. Een omgekeerde lijst van n waarden heeft elk paar omgekeerd, n(n − 1)/2 inversies, het slechtste geval.

Elke cel geeft vergelijkingen / verwisselingen. De voorbeeldlijst is [5, 1, 4, 2, 8]. Bubblesort is hier de versie die stopt na een doorgang zonder verwisseling.

Alle drie methoden hebben dezelfde zwakte. In het slechtste geval vergelijken ze ongeveer elk paar waarden, zo'n n²/2 vergelijkingen. Verdubbel de lijst en het werk wordt viermaal zo groot. Een tienmaal zo grote lijst betekent honderdmaal zoveel werk. Voor enkele tientallen waarden maakt dat nauwelijks uit; voor een miljoen is het hopeloos. In het volgende hoofdstuk zie je hoe het veel beter kan.