Home
Achtergrond
Sorteeralgoritmes: waarom Timsort zo snel is

Development

Sorteeralgoritmes: waarom Timsort zo snel is

Marco den Teuling Marco den Teuling Vandaag

Bij het aanroepen van sort() zorgt Timsort bij veel programmeertalen voor het efficiënt ordenen van lijstelementen in de juiste volgorde. We bekijken hoe Timsort geprogrammeerd is en waarom dat algoritme zo snel is.

Slimmer sorteren met Timsort

Hoe de algoritmen Bubblesort, Mergesort en Quicksort getallen sorteren in lijsten was het onderwerp van een eerder artikel. Met de langzame methode Bubblesort als voorbeeld lieten we zien wat de runtime (O-notatie) van een methode is. We gingen ook in op de details, legden uit wat in-place betekent en wat het verschil is tussen een stabiel en een instabiel sorteeralgoritme.

Met Mergesort en Quicksort hebben we twee snelle sorteeralgoritmen gedemonstreerd die beide gebaseerd zijn op het verdeel-en-heers principe. Hoewel Quicksort en Mergesort zeker niet traag zijn met een gemiddelde runtime van O(n log n), sorteren beide onvoorwaardelijk volgens hun schema en negeren ze daarbij de oplopende of aflopende reeksen die vaak al voorkomen in echte datasets. Het Timsort-sorteeralgoritme maakt daarentegen wel gebruik van dergelijke opeenvolgende delen. Dat sorteeralgoritme bestaat pas sinds 2002. De ingebouwde sort()-functie van veel programmeertalen maakte lange tijd gebruik van Timsort.

Insertionsort

Voordat we aan de slag gaan, moeten we eerst een paar relevante onderdelen van Timsort uitleggen. Te beginnen met Insertionsort, een eenvoudig sorteeralgoritme dat wisseloperaties uitvoert vergelijkbaar met Bubblesort.

Insertionsort behandelt de lijst alsof die uit twee secties bestaat: een gesorteerde sectie aan het begin van de lijst en een ongesorteerde sectie aan het einde. In plaats van de grootste waarde naar het einde van de lijst te laten stijgen, zoals Bubblesort doet, verplaatst Insertionsort een ongesorteerd element echter naar de juiste positie in de gesorteerde sectie.

Dat betekent dat Insertionsort minder vergelijkingen nodig heeft en daarom in de praktijk sneller is, ook al staat het qua runtime-complexiteit met O(n²) op hetzelfde niveau als Bubblesort.

De ruwe procedure is eenvoudig te begrijpen aan de hand van de getallenreeks 2 4 6 1 3. Het eerste element kan triviaal door Insertionsort worden beschouwd als al gesorteerd en het eigenlijke sorteerproces kan worden gestart met het tweede element.

Lees dit artikel verder

Lees over tech-trends en achtergronden, nieuwe apparatuur, software en toepassingen voor professioneel gebruik. Met c’t heb je altijd de juiste tech-informatie. Word abonnee en lees onbeperkt alle artikelen.

Bekijk abonnementen Al abonnee? Log in

Omdat de opeenvolgende getallen 4 en 6 al in oplopende volgorde staan, wordt het invoegpunt pas actief bij 1. Het algoritme neemt die waarde en verplaatst die naar de juiste positie, helemaal bij het begin:

1 <-----------------------------------

2 4 6 _ 3

Om de waarde in te voegen en het gat te dichten, worden alle elementen vóór de 1 naar rechts verplaatst en wordt de waarde op de juiste positie ingevoegd:

1 2 4 6 3

Dat proces herhaalt zich voor de 3 en daarna is de lijst gesorteerd. Net als bij de algoritmes uit het vorige artikel, hebben we Insertionsort nagebouwd in Python:

for i in range(1, len(a)):
j = i
while j > 0 en a[j-1] > a[j]:

# Wissel van plaats 
buffer = a[j]
a[j] = a[j-1]
a[j-1] = buffer
j -= 1

Insertionsort gebruikt twee pointers: i loopt door de lijst en benadert elk element één voor één. j wordt daarentegen gebruikt telkens als een ongesorteerd element naar de juiste positie moet worden verplaatst.

Omdat Insertionsort stabiel en in-place werkt, is het ondanks de langere runtime geschikt voor bepaalde doeleinden, bijvoorbeeld om nieuw binnenkomende gegevens direct in een gesorteerde lijst te plaatsen.

Insertionsort presteert ook goed in grotendeels gesorteerde lijsten, omdat het grote delen van de lijst ongemoeid kan laten en alleen de paar ongesorteerde elementen naar de juiste positie hoeft te verplaatsen.

Binair zoeken

In zijn huidige vorm vereist Insertionsort veel vergelijkingen totdat het een element van het ongesorteerde gedeelte naar de juiste positie verplaatst heeft. Je kunt het aantal van dergelijke vergelijkingen verminderen door de invoegpositie sneller te vinden.

Een van de beste methoden hiervoor is binair zoeken, een ander algoritme uit de categorie ‘verdeel en heers’. Op weg naar Timsort bekijken we dat daarom eerst nog even.

Binair zoeken vindt een gezocht element of een invoegpositie in een gesorteerde lijst extreem snel met een runtime van O(log n). Het algoritme bootst de menselijke aanpak een beetje na als je bijvoorbeeld een naam wilt opzoeken in een alfabetisch gesorteerd telefoonboek.

Eerst sla je het boek ongeveer in het midden open en kijk je of de naam die je zoekt in de linker- of rechterhelft staat. Op die manier sorteer je bij elke run direct de helft van de mogelijke resultaten uit. Herhaal dat tot je de naam vindt die je zoekt.

Stel dat je 5 wilt vinden in deze lijst: 0 1 2 3 4 5 6 7. Bepaal eerst het midden van de lijst door de lengte door twee te delen en naar beneden af te ronden (8 / 2 = 4). Vergelijk dan het element op de vierde positie met het getal 5 dat je zoekt en kijk of je verder moet zoeken in de linker- of rechterhelft van de lijst.

Omdat 3 kleiner is dan 5, gaat het zoeken verder in de rechterhelft 4 5 6 7. Het nieuwe middelpunt daarvan zou 4 / 2 = 2 zijn, oftewel het getal op de tweede positie, dat al het element 5 is dat je zoekt.

In tegenstelling tot de lineaire zoekactie, die in dit voorbeeld zes vergelijkingen nodig zou hebben, vindt de binaire zoekactie het gezochte element met slechts twee vergelijkingen.

Je kunt zien hoe de iteratieve binaire zoekactie er in Python uit zou zien:

def binary_search(a, l, r, n):

while l <= r:

m = (l + r) // 2 # Bereken midden

if a[m] == n:

return m # Positie gevonden

if a[m] > n:

# verder zoeken in linkerhelft

r = m - 1

else:

# verder zoeken in rechterhelft

l = m + 1

return l # invoegpositie

Timsort

Met Insertionsort, binair zoeken en de informatie uit het eerdere artikel, ken je alle onderdelen van Timsort. De methode is in 2002 ontworpen door ontwikkelaar Tim Peters, die onder andere een sleutelrol heeft gespeeld in Python. Voor de grap noemde hij het sorteeralgoritme naar zichzelf.

Na het analyseren van veel echte datasets viel het hem op dat bijna geen enkele methode al oplopende of aflopende reeksen benutte. Zijn sorteeralgoritme maakt gebruik van dergelijke reeksen door binaire Insertionsort en de samenvoegfase van Mergesort te combineren.

Zoals Peters zelf schrijft in zijn gedetailleerde uitleg van Timsort, bevat het ook een heleboel kleine optimalisaties en randgevallen die andere ontwikkelaars hadden voorgesteld à la “Zou mooi zijn als sort() dit speciale geval zou afdekken… “. Je kunt weblinks naar zijn uitleg, andere bronnen over Timsort en onze GitHub-repository vinden via de link bij dit artikel.

We leggen hier de belangrijkste concepten van Timsort uit en programmeren ook een vereenvoudigde versie in Python met de componenten die al bekend zijn. Het valt buiten het bestek van dit artikel om op alle optimalisaties in te gaan.

Een complete implementatie van Timsort in Python (636 regels code) met alle kleine verbeteringen is te vinden in een oudere versie van de Python-bibliotheek pypy. Timsort wordt voor de efficiëntie geprogrammeerd in C en bestaat uit ongeveer 4200 regels code.

Timsort en al zijn kleine optimalisaties zijn alleen de moeite waard voor echt grote hoeveelheden gegevens, daarom laat de Python-implementatie lijsten met minder dan 64 elementen gewoon over aan Binary-Insertionsort.

Timsort doorloopt langere lijsten één keer van links naar rechts en zoekt naar delen die al gesorteerd zijn. Aan het eind worden alle afzonderlijke sublijsten samengevoegd met merge() uit Mergesort.

In Timsort worden die delen runs genoemd. Ze kunnen oplopend (a<0 <=a1 <= a2 of strikt aflopend (a0 > a1 > > a2) zijn. Aflopende reeksen mogen geen identieke elementen bevatten omdat anders de oorspronkelijke reeks verloren zou gaan als de reeks wordt omgekeerd en het proces niet langer stabiel zou zijn.

In ons Python-programma vindt de methode find_run() dergelijke secties.

def find_run(a, l):

n = len(a)

descending = False

# de run wordt beëindigd,

# als het laatste element bereikt is

if l == n - 1:

return 1, False

# True, als de lijst aflopend is

if a[l] > a[l + 1]:

descending = True

# Elementen tellen

i = l # startindex

if descending:

while i+1 < n and a[i] > a[i+1]:

i += 1 # aflopend

else:

while i+1 < n and a[i] <= a[i+1]:

i += 1 # oplopend

return i - l + 1, descending

De methode geeft twee waarden terug: het aantal elementen in een volgende reeks vanaf de startpositie l en een waarde (descending) die aangeeft of de gevonden volgende reeks aflopend of oplopend was. De inversie van een aflopende reeks vindt plaats in de eigenlijke timsort()-methode, die je kunt zien in het kader met code.

def timsort(a):

n = len(a)

# als array kleiner dan 64,

# dan alleen Binary-Insertionsort gebruiken

if n < 64:

insertionsort(a, 0, n)

return a

minrun = calc_minrun(n)

# run doorlopen

runs = []

i = 0 # startindex

while i < n:

# lengte en richting voor de volgende run opvragen

run_len, descending = find_run(a, i)

# aflopende run omkeren

if descending:

a[i:i + run_len] = reversed(a[i:i + run_len])

# run verlengen tot lengte van minrun

if run_len < minrun:

elements_left = min(minrun, n - i)

insertionsort(a, i, i + elements_left)

run_len = elements_left

runs.append((i, run_len))

i += run_len

# runs samenvoegen

while len(runs) > 1:

new_runs = []

# run[i] met run[i+1] mergen

for i in range(0, len(runs), 2):

if i + 1 < len(runs):

l1, len1 = runs[i] # eerste run

l2, len2 = runs[i + 1] # tweede run

# aangrenzende runs mergen

merge(a, l1, l2, l2 + len2)

# nieuwe run bepalen

new_runs.append((l1, len1 + len2))

else:

# oneven run blijft over

new_runs.append(runs[i])

# oude run vervangen door nieuwe samenvoeging

runs = new_runs

return a

Als een run niet lang genoeg is, verlengt Timsort die kunstmatig door delen ervan met Binary-Insertionsort te sorteren om een minimale run-grootte te bereiken. In het origineel heet de variabele daarvoor minrun. De waarde van die variabele hangt af van de hoeveelheid gegevens zodat Timsort zo efficiënt mogelijk werkt.

In de praktijk ligt minrun vaak tussen 32 en 64 omdat een vaste keuze van bijvoorbeeld 32 onder bepaalde omstandigheden kan leiden tot een onnodig groot aantal vergelijkingen. Tim Peters geeft daar een concreet voorbeeld voor in zijn uitleg.

Ervan uitgaande dat de lijst een lengte van 2112 heeft, zou Timsort 66 runs met een lengte van 32 ontvangen. De eerste 64 runs zouden perfect samengevoegd kunnen worden, maar dan blijven er 2048 gesorteerde elementen en 64 ongesorteerde elementen over die opnieuw samengevoegd moeten worden.

Dat kost vergelijkingen die vermeden kunnen worden met een minrun-waarde van 33, omdat de lijst dan wordt opgesplitst in 64 runs met lengte 33.

Tot zover het maken van de runs. Trouw aan het principe van ‘verdeel en heers’, moeten de individuele sublijsten dan weer aan elkaar gekoppeld worden. Onze vereenvoudigde Timsort-implementatie combineert altijd twee aangrenzende runs met elkaar.

In de praktijk gebruikt Timsort twee extra optimalisaties die niet triviaal zijn om te programmeren: de merge-stack en galloping. Voor de inzichtelijkheid hebben we beide weggelaten in de voorbeeldcode.

Aan de ene kant wil je zo snel mogelijk samenvoegen, aan de andere kant wil je beter plannen voor lange runs met veel gesorteerde elementen. De merge-stack-optimalisatie van Timsort gebruikt daarom een compromis en beheert runs in een stapel (stack) die deze regels volgt:

A > B+C
B > C

De lengtes van de verschillende runs worden daarbij vergeleken. Als er drie runs in de stack zitten (A onderaan, B in het midden en C bovenaan), kunnen alleen aangrenzende runs worden samengevoegd (A + B of B + C). Met die regels coördineert Timsort de lengte van de runs en wordt voorkomen dat kleine runs te laat worden samengevoegd met hele grote runs, wat veel vergelijkingen en dus prestaties zou kosten.

De tweede optimalisatie komt aan het licht bij het samenvoegen van twee runs. Soms komt het voor dat een lijst een bijzonder groot aantal elementen achter elkaar levert, wat betekent dat die veel vergelijkingen achter elkaar ‘wint’.

In het ergste geval kunnen bijna alle getallen van dezelfde lijst komen voordat de volgende run weer aan de beurt is. Dat kost een onnodig aantal vergelijkingen tussen de twee lijsten. Het zou daarom beter zijn om van tevoren te controleren hoe vaak run A wint voordat run B weer aan de beurt is en alle betreffende elementen uit de lijst in één keer over te zetten.

Een vereenvoudigd voorbeeld met twee runs illustreert dat principe:

A: 0, 1, 2, 3, 4 ... 100

B: 100, 101, 102 ... 199

In dit extreme voorbeeld zou run A meer dan 100 elementen leveren voordat Run B aan de beurt is. In plaats van 100 paren elementen te vergelijken, kijkt Timsort na 7 opeenvolgende overwinningen van lijst A eerst hoeveel keer A nog wint voordat B weer aan de beurt is. Het kan dan al deze elementen in één keer samenvoegen, wat een hoop vergelijkingen bespaart.

Afhankelijk van hoe succesvol dit galopping is, wordt de drempelwaarde dynamisch aangepast.

Er zijn echter ook gevallen waarin galopping niet de moeite waard is en die worden daarom onderschept in het eigenlijke Timsort. Timsort gebruikt ook niet slechts één samenvoegmethode, maar verschillende om echt elke kleine optimalisatie eruit te halen. Meer hierover in de uitleg van Tim Peters – zie de link.

In het beste geval heeft Timsort een runtime van O(n), in het gemiddelde en slechtste geval hetzelfde als Mergesort: O(n log n). In de praktijk blijkt dat Timsort echter iets sneller loopt dan Mergesort, daarom zit het vanaf Python versie 2.3 tot 3.11 achter de sort()-aanroep. Ondertussen heeft een algoritme gebaseerd op Timsort genaamd Powersort die rol overgenomen.

Tot slot

Er zijn nog veel meer sorteeralgoritmen, die je zelf mag gaan ontdekken. Voorbeelden zijn Radixsort en een van de boomgebaseerde sorteeralgoritmen zoals Heapsort. Ook een variant van Heapsort genaamd Smoothsort is het bekijken waar, die is uitgevonden door de Nederlandse wiskundige en informaticus Edsger W. Dijkstra.

Dat beëindigt onze uitstap in de wereld van sorteeralgoritmen – in elk geval de serieuze. Als afsluiting komt nog een laatste artikel over een paar minder bruikbare en niet helemaal serieuze sorteeralgoritmen presenteren, zoals Stalinsort en Bogosort.

Wilhelm Drehling en Marco den Teuling

Overzicht van links bij dit artikel

Marco den Teuling

Had als eerste computer ooit een 16-bit systeem, waar van de 48 kilobyte toch echt niet ‘genoeg voor iedereen’ was. Heeft een brede interesse in tech en IT, van nieuwe hardware tot obscure softwaretools. Vindt ‘Software as a Service’ een onbedoeld ironische naamgeving.