Python Merge Sort-tutorial

Gegevens sorteren is een van de meest voorkomende handelingen die data professionals dagelijks uitvoeren. Vaak moeten we data in een bepaalde volgorde tonen om er betekenisvolle informatie uit te halen. Gelukkig hoeven we dit tegenwoordig niet meer handmatig te doen. Computers doen het zware werk voor ons met ongeëvenaarde prestaties.

Er zijn verschillende strategieën om data te sorteren. In deze tutorial analyseren we een van de meest effectieve sorteertechnieken. Het “merge sort”-algoritme gebruikt een divide-and-conquer-strategie om een ongesorteerde array te sorteren door deze eerst op te splitsen in kleinere arrays, die later in de juiste volgorde worden samengevoegd. 

In de volgende secties bespreken we alle details van het merge sort-algoritme, hoe het eruitziet in Python en enkele praktische tips voor een soepele implementatie.

Wat is Merge Sort?

Er zijn veel sorteeralgoritmen, maar het is lastig er één te vinden die beter presteert dan merge sort. Niet verrassend wordt dit algoritme in allerlei praktijksituaties gebruikt, zoals het sorteren van grote databases of het ordenen van bestanden op een gewone computer.

Het algoritme is gebaseerd op het divide-and-conquer-paradigma, dat kan worden opgesplitst in drie delen:

• Divide: dit proces verdeelt het probleem in kleinere subproblemen. 
• Conquer: de subproblemen worden recursief opgelost. 
• Combine: de oplossingen van de subproblemen worden gecombineerd om tot de uiteindelijke oplossing te komen.

Divide-and-conquer-strategie

Laten we bekijken hoe merge sort werkt. Stel dat we de volgende getallen willen ordenen met het merge sort-algoritme. Het algoritme splitst de data recursief in twee delen en blijft splitsen totdat elke lijst één element bevat. Vervolgens voegen we ze samen door ze in een andere lijst te sorteren.

Merge sort-probleem. Bron: DataCamp

Tijds- en ruimtecomplexiteit van Merge Sort

Het is onmogelijk om van tevoren te weten welk sorteeralgoritme het beste werkt voor een bepaald probleem. Er moeten verschillende variabelen in aanmerking worden genomen naast het algoritme, waaronder de programmeertaal waarin de code is geschreven, de hardware waarop deze wordt uitgevoerd en de bijzonderheden van de te sorteren data. 

Hoewel we de exacte uitvoeringstijd van een sorteeralgoritme niet kunnen voorspellen, kunnen we de prestaties van verschillende sorteeralgoritmen nog steeds vergelijken door tijds- en ruimtecomplexiteit te analyseren.

Tijdcomplexiteit van merge sort

Zoals we hebben uitgelegd in een aparte gids over Big O-notatie en tijdcomplexiteit, is het doel van tijdcomplexiteitsanalyse niet om de exacte looptijd van een algoritme te voorspellen, maar om te beoordelen hoe efficiënt een algoritme is door te analyseren hoe de looptijd verandert naarmate de hoeveelheid invoergegevens toeneemt.

Tijdcomplexiteitsanalyse wordt geschreven in Big O-notatie, een wiskundige notatie die de snelheid beschrijft waarmee een functie groeit of afneemt. Merge sort heeft een log-lineaire of lineair-logaritmische tijdcomplexiteit, genoteerd als O(N log(N)), waarbij N het aantal elementen in de lijst is. De letter 'O' staat voor de 'orde' van groei. 

In tijdcomplexiteitsanalyse gedraagt lineair-logaritmische complexiteit zich ongeveer vergelijkbaar met lineaire complexiteit, wat betekent dat de uitvoering direct evenredig is met de hoeveelheid data. Dus als de hoeveelheid data verdubbelt, zou ook de tijd die het algoritme nodig heeft om de data te verwerken ongeveer verdubbelen, oftewel het aantal splitsingen en samenvoegingen verdubbelt.

Omdat de tijdcomplexiteit van merge sort zich lineair gedraagt, blijft de complexiteit hetzelfde voor de beste, gemiddelde en slechtste gevallen. Dat betekent dat, ongeacht de inputvolgorde, het algoritme altijd hetzelfde aantal stappen nodig heeft om te voltooien.

Ruimtecomplexiteit van merge sort

Naast de tijd die nodig is om de taak te voltooien, is nog een belangrijk aspect bij het analyseren van algoritmecomplexiteit het inschatten hoeveel geheugen het algoritme nodig heeft naarmate het probleem groter wordt. 

Dit valt onder de concepten ruimtecomplexiteit en aanvullende ruimte. Het laatste verwijst naar de extra of tijdelijke ruimte die door een algoritme wordt gebruikt, terwijl het eerste verwijst naar de totale ruimte die door het algoritme wordt ingenomen ten opzichte van de invoergrootte. Met andere woorden, ruimtecomplexiteit omvat zowel aanvullende ruimte als de ruimte die door de input wordt gebruikt.

Merge sort heeft een ruimtecomplexiteit van O(N). Dit komt doordat het een aanvullende array van grootte N gebruikt om de gesorteerde helften van de inputarray samen te voegen. De aanvullende array wordt gebruikt om het samengevoegde resultaat op te slaan, en de inputarray wordt overschreven met het gesorteerde resultaat.

Merge Sort-implementatie in Python

Laten we het merge sort-algoritme in Python implementeren. Er zijn verschillende manieren om het algoritme te coderen; we blijven echter bij de recursieve variant, die waarschijnlijk het makkelijkst te begrijpen is en minder regels code vereist dan andere iteratieve alternatieven.

Recursie begrijpen in merge sort

Als je nieuw bent met dit onderwerp: in programmeren treedt recursie op wanneer een functie zichzelf aanroept. Bekijk onze Understanding Recursive Functions in Python-tutorial om alles te leren over deze krachtige functies.

Om merge sort te implementeren, definiëren we eerst het basisgeval: als de lijst slechts één element bevat, is deze al gesorteerd, dus we retourneren direct. Anders splitsen we de lijst in twee helften, left_half en right_half, en roepen we merge_sort() recursief op voor elk daarvan. Dit proces gaat door totdat alle sublijsten één element bevatten.

Zodra we deze gesorteerde sublijsten hebben, beginnen we met het samenvoegen. Hiervoor initialiseren we drie indexvariabelen: i om de positie in left_half bij te houden, j voor right_half, en k voor de uiteindelijke samengevoegde lijst. We vergelijken vervolgens elementen uit beide helften. Als het huidige element in left_half kleiner is, plaatsen we het in my_list[k] en verhogen we i. Anders nemen we het element uit right_half, plaatsen het in my_list[k] en verhogen j. Na elke vergelijking schuiven we k op naar de volgende positie in de eindlijst.

Dit proces gaat door totdat we alle elementen in een van de helften hebben vergeleken. Als er nog elementen overblijven in left_half of right_half, voegen we die direct toe aan de uiteindelijke lijst, zodat er geen gegevens achterblijven. Omdat merge sort recursief werkt, wordt dit samenvoegproces op elk niveau van de recursie uitgevoerd totdat de hele lijst is gesorteerd.

Python-implementatie

Hieronder vind je de code met de ongesorteerde lijst uit het vorige diagram als voorbeeld:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]Mogelijk gemaakt door

Merge Sort vs. andere sorteeralgoritmen

Merge sort is een vrij snel sorteeralgoritme, vooral geschikt voor grote databases, en het wordt vaak gebruikt als benchmark voor andere algoritmen. Voor kortere lijsten is de prestatie echter vaak lager dan die van andere sorteeralgoritmen.

In de volgende tabel vind je een vergelijking van merge sort met andere populaire sorteeralgoritmen.

Praktische toepassingen van Merge Sort

Merge sort presteert uitstekend bij het sorteren van grote lijsten, maar de efficiëntie neemt af bij kleinere lijsten. Evenzo is het vaak minder efficiënt in situaties waarin er al enige orde in de inputlijsten zit, aangezien merge sort dezelfde stappen uitvoert, ongeacht de volgorde van de lijst.

Een uitstekend toepassingsgebied waar merge sort bijzonder handig is, zijn linked lists. Een linked list is een datastructuur die bestaat uit een reeks knooppunten die lineair met elkaar verbonden zijn. Elk knooppunt bevat de data en de link naar het volgende knooppunt.

Merge sort heeft de voorkeur voor linked lists omdat het alleen sequentiële toegang tot data vereist, wat goed aansluit bij de aard van linked lists. Bovendien is merge sort een stabiel sorteeralgoritme (d.w.z. het behoudt de relatieve volgorde van gelijke elementen in de gesorteerde output), wat belangrijk is om de volgorde van linked lists te behouden.

Veelvoorkomende fouten en troubleshooting

Het merge sort-algoritme is vrij rechttoe rechtaan en de ruimte voor verbetering in de code is beperkt. Je kunt de complexiteit van je sorteersstrategie echter vergroten door rekening te houden met de grootte van de invoergegevens. 

We hebben al vastgesteld dat merge sort beter werkt met grotere datasets. Voor kleinere datasets kunnen andere sorteeralgoritmen met tijdcomplexiteit O(N^2), zoals insertion sort, beter werken. In dat geval hoef je alleen een drempelwaarde voor de grootte te definiëren waarboven je merge sort gebruikt en daaronder kiest voor insertion sort.

Daarnaast is parallelisatie een goed idee om te verkennen. De stappen van merge sort kunnen met de juiste rekenkracht gemakkelijk worden geparallelliseerd, waardoor de voltooiingstijd afneemt. Lees onze CPU vs GPU-gids om meer te leren over parallel computing. 

Conclusie

Merge sort is een van de meest effectieve en populaire sorteeralgoritmen, maar er valt nog veel meer te leren in het prachtige en steeds groter wordende universum van algoritmen. Als je geïnteresseerd bent in de technische kant van algoritmen, hoe ze werken en hun bijbehorende complexiteit, sterke punten en zwaktes, kunnen deze DataCamp-bronnen je helpen verder te leren:

• Introductie tot Data Structures and Algorithms-cursus 
• Python Programming Skill Track
• Python Data Fundamentals Skill Track
• Intermediate Python-cursus
• Data Analyst in Python Career Track 
• Big O-notatie en tijdcomplexiteit