Algoritmen: Merge Sort
1. Merge Sort
Voor de vakantie hebben we al eventjes geprobeert, spelkaarten te sorteren. Nu gaan we dit thema verdiepen door een “merge sort” aan te maken.
- “Merge sort” gaat eerst de te sorterende reeks opsplitsen, en dan bij het samenvoegen sorteren.
- Een reeks van maar één nummer is altijd gesorteerd.
- Die strategie noemt men ook “Divide and Conquer”.
- We kunnen dit best recursief aanpakken, een concept uit “functional programming”.
- Meer info: https://nl.wikipedia.org/wiki/Mergesort
Dit is wat ingewikkeld! MAAR: we hebben een beneden de algoritme gegeven.
- Jullie hebben duidelijke instructies (gedefinieerd, ondubbelzinnig, implementeerbaar).
- Volg de stappen!
- Werkbestand voor vandaag is hier: ../code/merge_sort.py
We gaan samen de volgende algoritme implementeren:
- We maken een functie aan.
- [1a] De “base case”: als er maar eentje overblijft, is het zeker gesorteerd. Geef dan gewoon de input-reeks terug.
- — Fase 1: “Split”, het opsplitsen —
- [1b]… anders: splits het op in twee evenmatige reksen
- [2] vind het middelpunt van de reeks, als index
- [3] splits de reeks op in twee deelreeksen: een linke en een rechte
- [4] ga zeker dat de deelreeksen gesorteerd zijn: verwerk ze eens met de functie `mijnMergeSort(reeks)`!
- — Fase 2: “Merge”, het samenvoegen —
- [5] twee indices aanmaken, eentje voor de “linke” helft, eentje voor “rechts”; allebij starten bij null.
- [6] maak er een lege “result” lijst aan.
- [7] ga door een “while” loop, die kijkt of een van de indices al volledig door de bijhorende reeks gegaan is (dus, kijk dat de index kleiner is als de lengte van links|rechts).
- [8] vergelijk de elementen links en rechts.
- [9] als het element links kleiner is dan rechts, voeg het aan het resultaat
- [10] en verhoog de linkse loopindex om 1.
- [11+12] anders voeg het rechte element aan, en verhoog de rechtse index
- [8] vergelijk de elementen links en rechts.
- [13] dan moeten we nog de overblijfsels van “links” en “rechts” aan het “result” aanvoegen
- [14] geef het resultaat terug.
- [15] einde van de les: upload python-bestand → smartschool
2. Puzzel Rand
2.1. opdracht
opdracht vorige les:
- Bedenk (en schrijf) een algoritme om het aandeel randdelen in een rechthoekige puzzel te berekenen.
- Noot: dit hangt af van de puzzelgrootte en de aspectverhouding.
- Definitie “rand”: een deel dat maximaal drie buurdelen heeft.
- Alle deeltjes zijn even groot.
2.2. algoritme
Hier een mogelijke algoritme:
- Neem de puzzelgrootte
gen aspectverhoudingv. - Ga zeker dat deze allebei groter dan null zijn.
- Bereken de hoogte met de formule:
h = sqrt(g*v) - Bereken de basis met de formule:
b = round(g/h) - Corrigeer de puzzelgrootte indien het afronden tot een fout leidt, en geef er een waarschuwing aan de gebruiker.
- Bereken de omtrek/rand met de formule:
r = 2*(b+h) - 4 - Het resultaat is de verhouding van omtrek en puzzelgrootte:
return r/g
2.3. oplossing
We gebruiken de volgende bibliotheken:
import numpy # numerieke berekening, zoals afronden en de vierkantewortel from warnings import warn as Warn # waarschuwingen
Er was een foutje in mijn bordberekeningen, sorry!
Met een gegeven puzzelgrootte \(g\) en aspectverhouding \(v\) kunnen we de zijkantenlengtes (\(b,\ h\) voor basis en hoogte) berekenen. We weten: \[g = b \cdot h\] \[v = \frac{b}{h}\quad \Leftrightarrow \quad b = v \cdot h\]
Als we de tweede vergelijking omgevormt in de eerste steken krijgen we: \[g = b \cdot h = v \cdot h^2\] \[b = +\sqrt{\frac{g}{v}}\]
Of: \[v = \frac{b}{h}\quad \Leftrightarrow \quad h = \frac{b}{v}\] \[g = b \cdot h = \frac{b^2}{v}\] \[h = +\sqrt{g\cdot v}\]
Dit kunnen we in een python-functie brengen:
def BerekenZijkanten(grootte: int, aspectverhouding: float) -> (int, int): # bereken de zijkantenlengtes van een gegeven grootte en aspectverhouding # formule van boven # zeker gaan dat er geen te kleine puzzelkanten uitkomen, minimum-hoogte is 1 hoogte = max([1, int(numpy.round(numpy.sqrt(grootte * aspectverhouding)))]) # en de andere kant volgt eruit basis = int(grootte / hoogte) # eventjes checken of het resultaat klopt if grootte != basis * hoogte: Warn(f"De aspectverhouding {aspectverhouding} geeft bij een puzzelgrootte {grootte} geen gehele kanten; benadering door aangepaste puzzelgrootte {basis} * {hoogte} = {basis*hoogte}.") return basis, hoogte # een kleine test is altijd goed, zie afbeelding boven print (BerekenZijkanten(int(6*4), 6/4))
Dit kunnen we voor een stap in de algoritme gemakkelijk overnemen:
def RandAanDeel(puzzelgrootte: int, aspectverhouding: float) -> float: # gebruiksfouten opsporen if aspectverhouding <= 0: raise IOError(f"De aspectverhouding moet echt groter dan 0 zijn; {aspectverhouding} is niet mogelijk.") if puzzelgrootte <= 0: raise IOError(f"De puzzelgrootte moet groter dan 0 zijn; {puzzelgrootte} is niet mogelijk.") # zijkanten berekenen basis, hoogte = BerekenZijkanten(puzzelgrootte, aspectverhouding) # de puzzelgrootte zeker aanpassen grootte_benadering = basis * hoogte # vier hoekstukken zijn deel van de basiskant en de hoogte, # tenzij dat we een extreme aspectverhouding hebben hoekstukken = 4 / (1 if basis > 1 else 2) / (1 if hoogte > 1 else 2) # bereken de rand if (basis > 1 and hoogte > 1): rand = (basis+hoogte)*2 - hoekstukken else: # indien de aspectverhouding extreem is, dan hebben we niet echt een "omtrek" rand = basis * hoogte # en de uitkomst return rand/grootte_benadering # en weer een kleine test print (' 24, 1.50:', RandAanDeel(int(6*4), 6/4)) print (' 24, 0.01:', RandAanDeel(int(6*4), 0.01)) print ('100, 1.50:', RandAanDeel(100, 6/4)) print (' 1, 0.67:', RandAanDeel(1, 4/6))
24, 1.50: 0.6666666666666666 24, 0.01: 1.0 100, 1.50: 0.375 1, 0.67: 1.0
Bonusopdracht voor gevoorderden:
- Probeer er een reeks van puzzelgrootten en aspectverhoudingen.
- Maak er een afbeelding aan van de samenhang van die twee parameters en de randaandeel (3D surface plot:
r = f(g, v)).
vorige les \(\quad\) volgende les