Python Merge Sort Zelfstudie

Het sorteren van gegevens is een van de meest voorkomende handelingen die datapractitioners dagelijks uitvoeren. Vaak moeten we gegevens in een bepaalde volgorde weergeven om zinvolle informatie te extraheren. Gelukkig hoeven we tegenwoordig deze taak niet meer handmatig uit te voeren. Computers kunnen het magische werk voor ons doen met onovertroffen prestaties.

Er zijn verschillende strategieën om gegevens te sorteren. In deze tutorial zullen we een van de meest effectieve sorteertechnieken analyseren. Het “merge sort”-algoritme maakt gebruik van een verdeel-en-heers strategie om een ongesorteerde array te sorteren door deze eerst in kleinere arrays op te splitsen, die later in de juiste volgorde worden samengevoegd.

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

Wat is Merge Sort?

Er zijn veel sorteeralgoritmen, maar het is moeilijk om er een te vinden die beter presteert dan merge sort. Verrassend genoeg wordt dit algoritme gebruikt in allerlei real-world toepassingen, zoals het sorteren van grote databases of het organiseren van bestanden op een gewone computer.

Het algoritme is gebaseerd op het verdeel-en-heers paradigma, dat kan worden opgesplitst in drie delen:

• Verdeel: dit proces verdeelt het probleem in kleinere deelproblemen.
• Heers: de deelproblemen worden recursief opgelost.
• Combineer: de oplossingen van de deelproblemen worden gecombineerd om de uiteindelijke oplossing te bereiken.

Verdeel-en-heers strategie

Laten we eens kijken hoe merge sort werkt. Stel dat we de volgende getallen willen ordenen door het toepassen van het merge sort algoritme. Het algoritme verdeelt de data recursief in twee delen en blijft verdelen totdat elke lijst één element heeft. Vervolgens combineren we ze door ze te sorteren in een andere lijst.

Merge Sort Probleem. Bron: DataCamp

Tijd- en ruimtecomplexiteit van Merge Sort

Het is onmogelijk om van tevoren te weten welk sorteeralgoritme het beste werkt voor een bepaald probleem. Verschillende variabelen moeten worden overwogen, naast het algoritme, waaronder de programmeertaal die wordt gebruikt om de code te schrijven, de hardware waarin ze worden uitgevoerd, en de bijzonderheden van de gegevens die moeten worden gesorteerd. 

Hoewel we de exacte looptijd van een sorteeralgoritme niet kunnen voorspellen, kunnen we nog steeds de prestaties van verschillende sorteeralgoritmen vergelijken door de tijd- 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 eerder om te evalueren hoe efficiënt een algoritme is door te analyseren hoe de looptijd verandert naarmate de hoeveelheid invoergegevens toeneemt.

Tijdcomplexiteitsanalyse is geschreven in de Big O-notatie, een wiskundige notatie die de snelheid beschrijft waarmee een functie groeit of afneemt. De merge sort heeft log-lineaire of lineairithmische tijdcomplexiteit, aangeduid als O(N log(N)), waarbij N het aantal elementen in de lijst is. De letter ‘O’ staat voor de ‘orde’ van groei. 

Bij tijdcomplexiteitsanalyse gedraagt lineairithmische complexiteit zich ongeveer hetzelfde als lineaire complexiteit, wat betekent dat de uitvoering recht evenredig zal zijn met de hoeveelheid gegevens. Dus als de hoeveelheid gegevens verdubbelt, zou de tijd die het algoritme nodig heeft om de gegevens te verwerken ook moeten verdubbelen, d.w.z. het aantal delingen en samenvoegingen zal verdubbelen.

Omdat de tijdcomplexiteit van merge sort lineair is, blijft de complexiteit hetzelfde voor de beste, gemiddelde en slechtste gevallen. Dat betekent dat, ongeacht de invoervolgorde, het algoritme altijd hetzelfde aantal stappen zal nemen om te voltooien.

Ruimtecomplexiteit van merge sort

Tenslotte, naast de tijd die nodig is om de taak te voltooien, is een ander belangrijk aspect bij het analyseren van algoritme complexiteit het schatten van hoeveel geheugen het algoritme nodig zal hebben om te voltooien naarmate het probleem groter wordt.

Dit valt onder de begrippen ruimtecomplexiteit en hulpruimte. De laatste verwijst naar de extra ruimte of tijdelijke ruimte die wordt gebruikt door een algoritme, terwijl de eerste verwijst naar de totale ruimte die wordt ingenomen door het algoritme met betrekking tot de invoergrootte. Met andere woorden, ruimtecomplexiteit omvat zowel hulpruimte als ruimte die wordt gebruikt door de invoer.

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

Implementatie van Merge Sort in Python

Laten we het merge sort algoritme implementeren in Python. Er zijn verschillende manieren om het algoritme te coderen; we zullen echter vasthouden aan de versie gebaseerd op recursie, die naar verluidt het gemakkelijkst te begrijpen is en minder regels code vereist dan andere alternatieven gebaseerd op iteratie.

Begrip van recursie in merge sort

Als je nieuw bent met het onderwerp, gebeurt recursie in de programmering wanneer een functie zichzelf aanroept. Je kunt onze Begrijpen van Recursieve Functies in Python Tutorial bekijken 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 geven we onmiddellijk terug. Anders splitsen we de lijst in twee helften, left_half en right_half, en roepen we merge_sort() recursief aan voor elk van hen. Dit proces gaat door totdat alle sublijsten één element bevatten.

Zodra we deze gesorteerde sublijsten hebben, beginnen we het samenvoegingsproces. Hiervoor initialiseren we drie indexvariabelen: i voor het bijhouden van de positie in left_half, j voor right_half, en k voor de uiteindelijke samengevoegde lijst. Vervolgens vergelijken we elementen uit beide helften. Als het huidige element in left_half kleiner is, plaatsen we het in my_list[k] en verplaatsen we i naar voren. Anders nemen we het element van right_half, plaatsen het in my_list[k], en verhogen we j. Na elke vergelijking verplaatsen we k naar de volgende positie in de uiteindelijke lijst.

Dit proces gaat door totdat we alle elementen in een van de helften hebben vergeleken. Als er zich nog elementen bevinden in zowel left_half als right_half, voegen we ze rechtstreeks toe aan de uiteindelijke lijst, zodat er geen gegevens worden achtergelaten. Omdat merge sort recursief werkt, wordt dit samenvoegingsproces op elk niveau van recursie uitgevoerd totdat de volledige lijst is gesorteerd.

Python-implementatie

Hieronder vind je de code met behulp van de ongesorteerde lijst van 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]

Merge Sort versus Andere Sorteer algoritmes

Merge sort is een vrij snel sorteeralgoritme, vooral geschikt voor grote databases, en wordt vaak gebruikt als benchmark voor andere algoritmes. Echter, als het gaat om kortere lijsten, is de prestatie vaak lager dan die van andere sorteeralgoritmes.

In de onderstaande tabel vind je een vergelijking van merge sort met andere populaire sorteeralgoritmes.

Praktische toepassingen van Merge Sort

Merge sort presteert goed bij het sorteren van grote lijsten, maar de efficiëntie neemt af bij het werken met kleinere lijsten. Daarnaast is het minder efficiënt in scenario’s waarin de inputlijsten al enige mate van ordening hebben, omdat merge sort dezelfde stappen zal uitvoeren ongeacht de volgorde van de lijst.

Een geweldig gebruiksscenario waarin merge sort bijzonder handig is, zijn gelinkte lijsten. Een gelinkte lijst is een datastructuur die bestaat uit een verbinding van knooppunten die lineair met elkaar zijn verbonden. Elk knooppunt bevat de gegevens en de link om het te verbinden met het volgende knooppunt.

Merge sort wordt verkozen voor gelinkte lijsten omdat het alleen sequentiële toegang tot gegevens vereist, wat goed aansluit bij de aard van gelinkte lijsten. Bovendien is merge sort een stabiel sorteeralgoritme (d.w.z. het behoudt de relatieve volgorde van gelijke elementen in de gesorteerde output), wat een zeer belangrijke overweging is voor het behouden van de volgorde van gelinkte lijsten.

Veelvoorkomende Fouten en Problemen

Het merge sort algoritme is vrij eenvoudig en de ruimte voor verbetering in de code is beperkt. U kunt echter de complexiteit van uw sorteermethode verhogen door rekening te houden met de omvang van de invoergegevens. 

We hebben al vastgesteld dat merge sort beter werkt met grotere datasets. Voor kleinere datasets kunnen andere sorteeralgoritmen met een tijdscomplexiteit van O(N^2), zoals insertion sort, beter werken. In dat geval hoeft u alleen een drempelwaarde te creëren waarbij u in plaats van merge en sort voor het insertion sort algoritme kiest.

Een goed idee om te verkennen zou parallelisatie zijn. De stappen van merge sort kunnen gemakkelijk worden geparalleliseerd met de juiste rekencapaciteit, waardoor de tijd om te voltooien wordt verminderd. Lees onze CPU vs GPU gids om meer te weten te komen over parallel computing. 

Conclusie

Merge sort is een van de meest effectieve en populaire sorteeralgoritmen die er zijn, maar er is nog veel meer te leren in het prachtige en steeds groter wordende universum van algoritmen. Als je geïnteresseerd bent in de technische aspecten van algoritmen, hoe ze werken, en hun bijbehorende complexiteit, deugden en nadelen, kunnen deze DataCamp-bronnen je helpen om je leerproces voort te zetten:

• Introductie tot Datastructuren en Algoritmen Cursus 
• Python Programmeervaardigheden Track
• Python Data Fundamentals Track
• Intermediate Python Cursus
• Data Analist in Python Carrière Track 
• Big O-notatie en Tijdcomplexiteit