Cursus Classic Computer Science Algorithms PDF

Classic Computer Science Algorithms Lesnota’s Stijn Lievens Professionele Bachelor in de Toegepaste Informatica  Inhoudsopgave Inhoudsopgave...

Classic Computer Science Algorithms Lesnota’s Stijn Lievens Professionele Bachelor in de Toegepaste Informatica  Inhoudsopgave Inhoudsopgave i Voorwoord v 1 Zoeken en Sorteren 1 1.1 Zoeken in een Array........................ 1 1.1.1 Sequentieel Zoeken..................... 2 1.1.2 Binair Zoeken........................ 3 1.1.3 Sequentieel vs. Binair Zoeken............... 8 1.2 Sorteren van een Array....................... 12 1.2.1 Sorteren door Selectie.................... 13 1.2.2 Sorteren door Tussenvoegen................ 17 1.2.3 Sorteren door Samenvoegen................ 20 1.3 Oefeningen.............................. 25 2 Gelinkte lijsten 29 2.1 Specificatie.............................. 30 2.2 Implementatie van een Gelinkte Lijst............... 31 2.2.1 Implementatie van een Knoop............... 31 2.2.2 Implementatie van een gelinkte lijst........... 32 2.2.3 Het gebruik van ankercomponenten........... 36 2.3 Dubbelgelinkte lijsten........................ 38 2.4 Beschrijving en Implementatie van Stapels............ 39 2.4.1 Beschrijving van een Stapel................ 39 2.4.2 Implementatie van een Stapel............... 40 2.5 Toepassingen van Stapels...................... 44 2.5.1 Controleren van haakjes.................. 44 2.5.2 Waardebepaling van een rekenkundige uitdrukking.. 45 2.6 Oefeningen.............................. 53 Classic Computer Science Algorithms 16/09/2024 ii Inhoudsopgave 3 Hashtabellen 55 3.1 Hashtabellen............................. 56 3.2 Verwerken van de overlappingen................. 58 3.2.1 Gesloten hashing...................... 58 3.2.2 Open hashing........................ 61 3.3 Keuze van hashcode en hashfunctie............... 64 3.4 Oefeningen.............................. 66 4 Bomen 67 4.1 Terminologie m.b.t. bomen..................... 67 4.1.1 Oefeningen......................... 71 4.2 Datastructuren voor bomen.................... 71 4.2.1 Array-van-kinderen voorstelling............. 71 4.2.2 Eerste-kind-volgende-broer voorstelling......... 73 4.2.3 Oefeningen......................... 74 4.3 Recursie op bomen......................... 74 4.3.1 Alle toppen van een boom bezoeken........... 74 4.3.2 Eenvoudige berekeningen op bomen........... 76 4.3.3 Oefeningen......................... 77 4.4 Binaire bomen............................ 78 4.4.1 Definitie en eigenschappen................ 78 4.4.2 Voorstelling van een binaire boom............ 80 4.4.3 Alle toppen van een binaire boom bezoeken...... 82 4.4.4 Oefeningen......................... 84 4.5 Binaire zoekbomen......................... 85 4.5.1 Opzoeken van een sleutel in een binaire zoekboom.. 87 4.5.2 Toevoegen van een sleutel aan een binaire zoekboom. 89 4.5.3 Verwijderen van een sleutel uit een binaire zoekboom. 91 4.5.4 Tijdscomplexiteit van de bewerkingen.......... 93 4.5.5 Oefeningen......................... 94 4.6 Binaire hopen............................ 95 4.6.1 Prioriteitswachtrij...................... 95 4.6.2 Implementatie als binaire hoop.............. 96 4.6.3 Implementatie........................ 97 4.6.4 Opzoeken van het element met de kleinste sleutel... 98 4.6.5 Toevoegen van een element................ 99 4.6.6 Verwijderen van het element met de kleinste sleutel.. 101 4.6.7 Tijdscomplexiteit van de bewerkingen.......... 103 Classic Computer Science Algorithms 16/09/2024 iii Inhoudsopgave 4.6.8 Oefeningen......................... 103 5 Graafalgoritmes 105 5.1 Terminologie m.b.t. grafen..................... 105 5.1.1 Oefeningen......................... 109 5.2 Datastructuren voor grafen.................... 109 5.2.1 De adjacentiematrix..................... 109 5.2.2 De adjacentielijst-voorstelling............... 111 5.2.3 Oefeningen......................... 114 5.3 Zoeken in Grafen.......................... 115 5.3.1 Generiek Zoeken...................... 115 5.3.2 Breedte-Eerst Zoeken.................... 118 5.3.3 Diepte-Eerst Zoeken.................... 120 5.3.4 Toepassing: Topologisch Sorteren............. 122 5.3.5 Oefeningen......................... 128 5.4 Kortste Pad Algoritmen...................... 129 5.4.1 Kortste Pad in een Ongewogen Graaf.......... 129 5.4.2 Dijkstra’s Algoritme.................... 130 5.4.3 Oefeningen......................... 135 5.5 Minimale Kost Opspannende Bomen............... 136 5.5.1 Minimale Kost Opspannende Bomen........... 136 5.5.2 Prims Algoritme....................... 137 5.5.3 Kruskals Algoritme..................... 139 5.5.4 Oefeningen......................... 141 5.6 Het Handelsreizigersprobleem.................. 141 5.6.1 Oefeningen......................... 145 6 Zoekalgoritmes 146 6.1 Inleiding............................... 146 6.2 Algemene Zoekalgoritmen..................... 153 6.2.1 Boomgebaseerd Zoeken.................. 153 6.2.2 Criteria voor Zoekalgoritmen............... 155 6.2.3 Graafgebaseerd Zoeken.................. 157 6.3 Blinde Zoekmethoden....................... 159 6.3.1 Breedte Eerst Zoeken.................... 159 6.3.2 Diepte Eerst Zoeken.................... 161 6.3.3 Iteratief Verdiepen..................... 163 6.3.4 Uniforme Kost Zoeken................... 168 6.4 Geïnformeerde Zoekmethoden.................. 170 Classic Computer Science Algorithms 16/09/2024 iv Inhoudsopgave 6.4.1 Heuristieken......................... 170 6.4.2 Gulzig Beste Eerst...................... 174 6.4.3 A∗ Zoekalgoritme...................... 175 6.5 Ontwerpen van Heuristieken................... 182 6.5.1 Gebruik van Vereenvoudigde Problemen........ 182 6.5.2 Patroon Databanken.................... 184 6.6 Oefeningen.............................. 185 A Complexiteitstheorie 190 A.1 De complexiteitsklasse P...................... 190 A.2 Reducties............................... 192 A.3 Compleetheid en de klasse NP.................. 193 A.4 De klasse P versus NP....................... 196 Classic Computer Science Algorithms 16/09/2024  Voorwoord Dit is de cursustekst voor het opleidingsonderdeel “Classic Computer Sci- ence Algorithms”, uit het tweede jaar professionele bachelor toegepaste in- formatica. Dit opleidingsonderdeel tracht enerzijds om jou wat extra (theoretisch) in- zicht bij te brengen in de werking van enkele belangrijke algoritmen en da- tastructuren. Anderzijds is het de bedoeling om te leren programmeren in Python. De tekst die nu voor je ligt wordt gebruikt in het “theoretische” deel van de cursus. Voor het praktische Python-deel wordt gebruikgemaakt van Dodona (dodona.ugent.be), een online leerplatform voor programmeren met ingebouwde automatische test- en feedbackmogelijkheden. Jullie ma- ken eveneens gebruik van de (Engelstalige) officiële Python-documentatie om jezelf de syntax van en het programmeren in Python eigen te maken. Daarnaast zijn er een tweetal inleidende lessen over Python. We durven ho- pen dat dit laatste vlot zal verlopen omdat Python als een eenvoudig te leren programmeertaal wordt beschouwd. Bovendien hebben jullie, als tweede- jaarsstudent, reeds een volledig jaar ervaring met programmeren in Java en Javascript. In de volgende paragrafen worden de verschillende hoofdstukken in de cur- sus kort overlopen. In het eerste hoofdstuk gebruiken we enkele algoritmen voor zoeken in en sorteren van arrays als aanknopingspunt voor een informele bespreking van tijdscomplexiteit van algoritmen. Het kennen (en eventueel verbeteren) van de tijdscomplexiteit van een algoritme is zeer belangrijk als je wenst dat je algoritme nog steeds performant werkt ook wanneer de invoer “groot” wordt, bv. wanneer de te sorteren array zeer lang wordt. In het tweede hoofdstuk introduceren we een eerste dynamische datastruc- tuur, nl. een gelinkte lijst. Het verschil met een “gewone” array is dat de Classic Computer Science Algorithms 16/09/2024 vi Inhoudsopgave verschillende elementen hier geen opeenvolgende plaatsen in het hoofdge- heugen innemen, maar dat er wordt gewerkt met referenties (pointers) om naar het volgende element in de lijst te wijzen. We tonen hoe zo’n gelinkte lijst kan geïmplementeerd worden. Als toepassing van een gelinkte lijst wordt een stapel geïmplementeerd. Dit is een zeer eenvoudige datastruc- tuur maar met krachtige toepassingen zoals het controleren van haakjes en het evalueren van uitdrukkingen in postfix notatie. In het derde hoofdstuk bekijken we hashtabellen en tonen aan hoe gelinkte lijsten kunnen aangewend worden om deze te realiseren. Hashtabellen zijn een zeer krachtige datastructuur en kunnen gebruikt worden om dictionary of Map-datastructuren mee te implementeren. Dictionaries zijn een zeer vaak gebruikte datastructuur in Python. In hoofdstuk 4 bestuderen we het concept van een “boom”. We bekijken verschillende types van bomen, bv. gewortelde bomen en binaire (zoek)bo- men, en bekijken hun toepassingen en implementatie. Deze implementa- tie gebeurt opnieuw vaak aan de hand van een dynamische datastructuur, maar nu zijn er typisch meerdere wijzers (pointers) per top. Hoofdstuk 5 veralgemeent in zekere zin het concept van een boom naar dat van een graaf. Grafen hebben een zeer ruim toepassingsgebied aangezien het in essentie gaat over het aangeven van relaties tussen verschillende ob- jecten. Eens men een bepaald probleem als een graaf heeft gemodelleerd dan komen sommige vragen vaak terug, zoals “welke andere objecten kun- nen we bereiken vanuit dit object? ”of “wat is de kortste weg tussen dit ob- ject en de andere objecten?”of “kunnen we deze objecten zodanig ordenen dat we enkel maar vooruit gaan?”. We tonen aan hoe deze vragen kunnen beantwoord worden a.d.h.v. enkele klassieke algoritmen zoals het algoritme van Dijkstra. In de marge van hoofdstuk 5 zien we ook dat er fundamentale verschillen zijn in de moeilijkheidsgraad van verschillende soorten van pro- blemen. Dit is het onderwerp van de appendix m.b.t. complexiteitstheorie. In hoofdstuk 6 bekijken we tenslotte hoe je “zoeken” kan aanpakken wan- neer het aantal toestanden (objecten) te groot wordt om in het hoofdgeheu- gen op te slaan. Je zal veel gelijkenissen ontdekken met hetgeen in hoofd- stuk 5 werd gezien, maar toch zijn er enkele belangrijke verschillen. We bestuderen het A∗ -algoritme waar je een vuistregel (een heuristiek) kan ge- bruiken om het zoeken efficiënter te laten verlopen terwijl je onder bepaalde omstandigheden nog steeds kan garanderen dat de gevonden oplossing op- Classic Computer Science Algorithms 16/09/2024 vii Inhoudsopgave timaal is. Zoals je waarschijnlijk al hebt gemerkt uit de voorgaande opsomming is het opleidingsonderdeel Classic Computer Science Algorithms relatief wiskun- dig en theoretisch. In deze tekst wordt de nadruk echter niet gelegd op de wiskundige bewijzen. Enkel wanneer deze kort zijn en helpen om de eigen- schap beter te begrijpen (en te onthouden) worden deze vermeld. Wanneer de bewijzen een meer wiskundige of theoretische inslag hebben worden ze in deze grootte afgedrukt. Het belangrijkste is echter dat je de eigenschappen kan toepassen. Hiertoe zijn een heel aantal oefeningen verwerkt in deze tekst. In de lessen zal je de kans krijgen om een aantal van deze oefeningen samen met je medestudenten en met hulp van de lesgever op te lossen. Het is zeer belangrijk dat je zelf de overige oefeningen en opgaven tracht te maken. Dat is de beste (zelfs enige?) manier om voldoende vertrouwd te geraken met de leerstof. Om te demonstreren dat de besproken algoritmen ook in de praktijk wer- ken voorzien we een aantal oefeningensessies op PC. Hierbij maken we, zo- als reeds hierboven vermeld, gebruik van de online programmeeromgeving Dodona en programmeren een aantal algoritmen in Python. Alvorens af te sluiten wens ik nog eens heel uitdrukkelijk collega Noemie Slaats hartelijk te bedanken. Zij was zo vriendelijk me de broncode van haar curusnota’s ter beschikking te stellen. De eerste drie hoofdstukken van deze curustekst zijn zeer sterk gebaseerd op bepaalde delen van de cursus Probleemoplossend Denken I (?) die tot het academiejaar 2019–2020 werd gegeven in de eerste bachelor toegepaste informatica. Ik bedank eveneens collega’s Pieter-Jan Maenhaut en Koen Mertens voor hun suggesties bij de tekst. Ik heb getracht de tekst met veel zorg te schrijven maar ongetwijfeld zijn er nog veel zaken voor verbetering vatbaar. Ik doe dan ook een warme oproep aan jullie, de studenten, om opmerkingen of aanmerkingen ter verbetering (bv. tikfouten, spellingsfouten, onduidelijkheden, enz.) aan te brengen. Ik zal jullie dankbaar zijn maar nog belangrijker: je opvolgers zullen je er even- eens dankbaar voor zijn. Voor het aangeven en bijhouden van errata zal er op Chamilo een forum worden aangemaakt. Alle fouten die vorig jaar wer- den gemeld op het forum zijn dit jaar aangepast in de cursus, dus jullie inspanningen voor het melden van errata worden zeker gewaardeerd. Classic Computer Science Algorithms 16/09/2024 viii Inhoudsopgave Tenslotte wens ik jullie veel lees-, leer- en oefenplezier. Stijn Lievens, september 2023 Classic Computer Science Algorithms 16/09/2024  H OOFDSTUK 1 Zoeken en Sorteren Zoeken in en sorteren van arrays zijn fundamentele algoritmen binnen de informatica. We starten met een bespreking van het meest eenvoudige zoekalgoritme, nl. LINEAIR ZOEKEN en zien ver- volgens hoe het zoekproces in een gesorteerde array significant sneller kan verlopen m.b.v. BINAIR ZOEKEN. Hieruit vloeit de na- tuurlijke vraag voort hoe men een array kan sorteren. We zien een tweetal “eenvoudige” sorteeralgoritmen, nl. SORTEREN DOOR SE - LECTIE en SORTEREN DOOR TUSSENVOEGEN die allebei een kwa- dratische uitvoeringstijd hebben. Wanneer de te sorteren rij lang wordt zijn deze algoritmen niet langer praktisch. M ERGESORT is een elegant sorteeralgoritme met een uitvoeringstijd van de orde O(n lg n). Doorheen het hoofdstuk geven we eveneens een infor- mele bespreking van de asymptotische uitvoeringstijden van de verschillende algoritmen. 1.1 Zoeken in een Array Een zoekalgoritme wordt gebruikt om een bepaald element te zoeken in een gegeven array, m.a.w. om de positie van dat element in de array te bepalen. Indien de array bij aanvang van het zoekproces reeds gesorteerd is, zal dit invloed hebben op de te gebruiken methode. In een ongesorteerde rij kan men minder efficiënt zoeken dan in een gesorteerde rij. Een bepaald woord opzoeken in een woordenboek gaat bijvoorbeeld snel en efficiënt aangezien een woordenboek een gesorteerde lijst van woorden is. Hetzelfde woord opzoeken in een willekeurig geordende lijst van woorden zal niet zo vlot verlopen. Classic Computer Science Algorithms 16/09/2024 2 Hoofdstuk 1. Zoeken en Sorteren Van een array veronderstellen we dat die de mogelijkheid heeft om elemen- ten op willekeurige plaatsen in constante tijd op te halen. Dit wil zeggen dat we veronderstellen dat het even snel gaat om het voorste, het laatste of een element in het midden van de array op te halen. We bekijken nu twee verschillende algoritmen om elementen op te zoeken in een array. 1.1.1 Sequentieel Zoeken Veronderstel dat je programma een lange array van namen bijhoudt, bij- voorbeeld de namen van 5000 studenten, waarbij de namen niet gesorteerd zijn. Als je wil weten of je eigen naam in de array voorkomt, dan is de meest voor de hand liggende manier om daarachter te komen het één voor één overlopen van alle namen uit de lijst (van voor naar achter) en kijken of jouw naam voorkomt. Deze manier van werken heet LINEAIR ZOEKEN of SEQUENTIEEL ZOEKEN. Lineair zoeken is gemakkelijk te implementeren. In de pseudocode in Algo- ritme 1.1 gaan we op zoek naar één specifiek item zoekItem in een array van items. De elementen van de array worden één voor één vergeleken met de op te sporen waarde zoekItem. Het algoritme stopt als er een element wordt gevonden dat gelijk is aan zoekItem of als het einde van de array bereikt is. De methode ZOEK S EQUENTIEEL verwacht twee inputwaarden: de waarde zoekItem en een array rij van lengte n. Als retourwaarde wordt de index van zoekItem teruggegeven, indien zoekItem niet voorkomt in de array is de retourwaarde −1. Meer specifiek vindt dit algoritme steeds het eerste voor- komen van de gezochte waarde zoekItem in de array. Opmerking 1.1 “Zoeken” is een proces dat onafhankelijk is van het type van de elementen in de array. In deze code wordt er enkel verondersteld dat we twee elementen met elkaar kunnen vergelijken om te beslissen of ze al dan niet gelijk zijn aan elkaar. Opmerking 1.2 (Assignatie en vergelijking) In de pseudocode gebruiken we a←b om de waarde van b toe te kennen aan a, m.a.w. het symbool ← wordt ge- bruikt voor assignatie. Vergelijken gebeurt met a=b Classic Computer Science Algorithms 16/09/2024 3 Hoofdstuk 1. Zoeken en Sorteren Algoritme 1.1 Sequentieel zoeken in een array. Invoer Een item zoekItem dat moet gevonden worden, een array van items genaamd rij met lengte n. Uitvoer de index van het eerste element in rij dat gelijk is aan zoekItem wordt teruggegeven of −1 indien zoekItem niet voorkomt in rij. 1: function Z OEK S EQUENTIEEL(zoekItem, rij) 2: i←0 ▷ overloopt de posities 3: while i < n and rij[i ] ̸= zoekItem do 4: i ← i+1 5: end while 6: if i = n then ▷ niet gevonden 7: index ← −1 8: else 9: index ← i ▷ gevonden 10: end if 11: return index 12: end function waarvan het resultaat een Booleanse waarde is. In het bijzonder is deze true wanneer a en b aan elkaar gelijk zijn en false wanneer dit niet het geval is. 1.1.2 Binair Zoeken Lineair of sequentieel zoeken is eenvoudig te implementeren en werkt ui- teraard ook als de array waarin wordt gezocht reeds gesorteerd is. Intuïtief is het echter duidelijk dat er een “betere” manier moet bestaan om te zoeken in een gesorteerde array. Voorbeeld 1.3 (Woordenboek) Wanneer mensen een woord willen opzoe- ken in een woordenboek dan slaat men het boek (ongeveer) in het midden open, kijkt of men te ver is of niet en bladert terug of verder. Na een paar po- gingen heeft men de juiste bladzijde voor zich liggen waarop het gezochte woord hopelijk voorkomt. Het probleem van het zoeken in een woorden- boek van honderden bladzijden is al heel snel gereduceerd tot het veel klei- nere probleem van het zoeken op één of twee bladzijden. Deze methode werkt natuurlijk alleen dankzij het feit dat de woorden in een woordenboek gesorteerd zijn. B INAIR ZOEKEN gaat op dezelfde manier tewerk als het zoeken in een woor- denboek, maar dan heel systematisch. In een gesorteerde array wordt het Classic Computer Science Algorithms 16/09/2024 4 Hoofdstuk 1. Zoeken en Sorteren middelste item bekeken. Als dit item kleiner is dan het gezochte item, wordt er verder gezocht in de rechterhelft van de array. In het andere geval wordt er verder gezocht in de linkerhelft van de array. Essentieel voor de perfor- mantie van binair zoeken is dat de array bij elke stap in (bijna) twee gelijke delen wordt verdeeld. Op het einde van dit proces blijft er precies één ele- ment over waarna de iteratie stopt. Door het vergelijken van dit ene element met het gezochte element weten we of het element voorkomt in de array of niet. Het idee dat het zoekproces in de oorspronkelijke array wordt herleid naar een zoekproces in een array half zo groot, laat toe dit probleem op te los- sen met recursie, maar uiteraard kan het algoritme ook iteratief worden geïmplementeerd. De twee verschillende mogelijke oplossingsmethodes, nl. a.d.h.v. iteratie en a.d.h.v. recursie, worden allebei besproken. Opmerking 1.4 Bij lineair zoeken was de enige vereiste aan het type van de elementen dat er kan beslist worden of ze gelijk zijn of niet. Bij binair zoeken is de array reeds gesorteerd (van klein naar groot). Dit betekent dat we voor twee elementen niet enkel moeten kunnen beslissen of ze gelijk zijn of niet, we moeten ook kunnen nagaan welke van de twee de grootste is als ze niet gelijk zijn. In de pseudocode schrijven we dit eenvoudigweg als: x < y. De in- en uitvoer van het algoritme voor binair zoeken is hetzelfde als de in- en uitvoer van het algoritme voor sequentieel zoeken. Opmerking 1.5 Bij de implementatie van binair zullen we wel wat aan- dacht besteden aan het feit dat de index van het eerste voorkomen in de array wordt geretourneerd zodat we steeds dezelfde retourwaarde krijgen als bij lineair zoeken. Er zijn echter ook implementaties van binair zoeken mogelijk die deze garantie niet geven. Om bij te houden welk deel van de array onderzocht moet worden, intro- duceren we de gehele variabelen l voor de positie links en r voor de positie rechts. Als zoekItem in de array voorkomt, dan komt zoekItem voor onder de elementen rij[l ], rij[l + 1],... , rij[r ]. Bij aanvang moet de volledige array onderzocht worden, dit betekent dat de variabelen l en r geïnitialiseerd moeten worden als volgt: l ← 0 en r ← Classic Computer Science Algorithms 16/09/2024 5 Hoofdstuk 1. Zoeken en Sorteren n − 1, waarbij n de lengte van de array voorstelt. Van het te onderzoeken deel wordt telkens het midden bepaald, de index van dit midden wordt bijgehouden in de gehele variabele m. Wanneer het aantal elementen in een rij oneven is, dan is het duidelijk wat het middelste element is, bv. voor de elementen rij, rij, rij, rij, rij. is het middelste element duidelijk rij. De index 7 wordt berekend als het gemiddelde van l = 5 en r = 9, want 7 = (5 + 9)/2. Wanneer het aantal elementen in een rij even is, bv. rij, rij, rij, rij, rij, rij dan zijn er twee “middelste” elementen. In het voorbeeld zijn dit rij en rij. We kiezen er in dit geval voor om het kleinste van deze twee elemen- ten als het middelste element aan te duiden. In dit geval is 5 + 10 7=⌊ ⌋. 2 Bijgevolgt kunnen we m in beide gevallen als volgt bepalen jl + rk m=. 2 Door de manier waarop m werd gedefinieerd geldt steeds dat l ≤ m < r. Het kan m.a.w. voorkomen dat m gelijk is aan l, maar m is steeds strikt kleiner dan r, wanneer l < r. In Algoritme 1.2 vindt men de iteratieve implementatie van het algoritme voor binair zoeken. Het binair zoekalgoritme kan ook recursief geïmplementeerd worden. Een recursief algoritme bevat steeds een selectiestructuur. Deze selectiestruc- tuur beschrijft wat er moet gebeuren in het basisgeval en wat er moet gebeu- ren in de recursieve stap. Basisstap: de te onderzoeken array bevat slechts één element. Dit element wordt vergeleken met de inputwaarde zoekItem. Classic Computer Science Algorithms 16/09/2024 6 Hoofdstuk 1. Zoeken en Sorteren Algoritme 1.2 Binair zoeken in een array geïmplementeerd m.b.v. iteratie. Invoer Een item zoekItem dat moet gevonden worden, een gesorteerde array genaamd rij van items van lengte n. Uitvoer de index van het eerste element in rij dat gelijk is aan zoekItem wordt teruggegeven of −1 indien zoekItem niet voorkomt in rij. 1: function Z OEK B INAIR(zoekItem, rij) 2: l←0 3: r ← n−1 4: while l ̸= r do ▷ herhalen totdat slechts één element overblijft l +r 5: m←⌊ 2 ⌋ 6: if rij[m] < zoekItem then 7: l ← m+1 ▷ in de rechterhelft zoeken 8: else 9: r←m ▷ in de linkerhelft zoeken 10: end if 11: end while ▷l=r 12: if rij[l ] = zoekItem then 13: index ← l ▷ gevonden 14: else 15: index ← −1 ▷ niet gevonden 16: end if 17: return index 18: end function Recursieve stap: de rij wordt gehalveerd. De functie wordt opnieuw aangeroepen op een deelrij half zo groot als de oorspronkelijke array. In Algoritme 1.3 vindt men de recursieve implementatie. Er is een “driver”- functie met de naam ZOEK B INAIR. Dit is de functie die wordt opgeroe- pen wanneer men een array wenst te sorteren. De functie ZOEK R ECURSIEF wordt opgeroepen door deze driver-functie en is de eigenlijke recursieve functie die het zoekproces implementeert. Opmerking 1.6 (Het eerste voorkomen) De gegeven implementatie zorgt ervoor dat het algoritme steeds het eerste voorkomen van een element vindt in de array. Deze garantie is niet langer geldig wanneer men de iteratie of recursie voortijdig zou afbreken op het moment dat men het gezochte ele- ment (voor de eerste maal) ontmoet. Classic Computer Science Algorithms 16/09/2024 7 Hoofdstuk 1. Zoeken en Sorteren Algoritme 1.3 Recursieve implementatie van binair zoeken. Invoer Een item zoekItem dat moet gevonden worden, een gesorteerde array genaamd rij van items van lengte n. Uitvoer de index van het eerste element in rij dat gelijk is aan zoekItem wordt teruggegeven of −1 indien zoekItem niet voorkomt in rij. 1: function ZOEK B INAIR(zoekItem, rij) 2: return ZOEK R ECURSIEF(zoekItem, rij, 0, n − 1) 3: end function Invoer Een item zoekItem dat moet gevonden worden, een gesorteerde array genaamd rij van items van lengte n, twee natuurlijke getallen l en r die het gedeelte van de array aangeven waarin gezocht moet worden. Uitvoer de index van het eerste element in rij dat gelijk is aan zoekItem wordt teruggegeven indien het element voorkomt tussen rij[l ], rij[l + 1],... , rij[r ]. De teruggeven index ligt dan tussen l en r. Er wordt −1 teruggegeven indien zoekItem niet voorkomt tussen de elementen rij[l ], rij[l + 1],... , rij[r ]. 4: function ZOEK R ECURSIEF(zoekItem, rij, l, r) 5: if l = r then ▷ basisstap, rij van lengte 1 6: if zoekItem = rij[l ] then 7: return l 8: else 9: return −1 10: end if 11: else ▷ inductiestap l +r 12: m←⌊ 2 ⌋ 13: if rij[m] < zoekItem then 14: return ZOEK R ECURSIEF(zoekItem, rij, m + 1, r) ▷ zoek rechts 15: else 16: return ZOEK R ECURSIEF(zoekItem, rij, l, m) ▷ zoek links 17: end if 18: end if 19: end function Classic Computer Science Algorithms 16/09/2024 8 Hoofdstuk 1. Zoeken en Sorteren 1.1.3 Sequentieel vs. Binair Zoeken Het algoritme voor binair zoeken is ingewikkelder om te implementeren dan het algoritme voor sequentieel zoeken. We hopen dat het algoritme voor binair zoeken dan ook “beter” is dan het algoritme voor sequentieel zoeken. Maar wat bedoelen we daar mee? Wanneer men algoritmen gaat analyseren dan is men doorgaans geïnteres- seerd in de volgende twee zaken: 1. De tijd die het algoritme nodig heeft wanneer het wordt uitgevoerd. 2. De hoeveelheid hoofdgeheugen (RAM) die het algoritme nodig heeft bij uitvoering. In deze cursus concentreren we ons voornamelijk op het analyseren van de uitvoeringstijd. Hierbij is vooral van belang om op te merken dat het niet zeer zinvol is om de uitvoeringstijd van een algoritme exact te (trachten) bepalen. Immers, Verschillende computers werken op verschillende snelheden. Ook op dezelfde computer zal in het algemeen het uitvoeren van het- zelfde algoritme op dezelfde input (lichtjes) verschillende uitvoerings- tijden opleveren, afhankelijk van welke andere processen er op dat moment nog draaien op de computer. Door het gebruik van steeds krachtigere programmeertalen is het soms moeilijk om te begrijpen welke en hoeveel instructies er precies zullen worden uitgevoerd. Om al deze redenenen beperkt men zich bij het analyseren van de uitvoe- ringstijd van algoritmen tot een ASYMPTOTISCHE ANALYSE van de uitvoe- ringstijd. Dit betekent dat men zich afvraagt welk gedrag de uitvoeringstijd vertoont voor “grote” waarden van de input. Typisch gedrag dat men zou kunnen zien is: Wanneer de invoer dubbel zo groot wordt, dan duurt het algoritme dubbel zo lang. De uitvoeringstijd gedraagt zich m.a.w. als een line- aire functie: T (n) = n. Classic Computer Science Algorithms 16/09/2024 9 Hoofdstuk 1. Zoeken en Sorteren Wanneer de invoer dubbel zo groot wordt, dan duurt het algoritme vier keer zo lang. De uitvoeringstijd gedraagt zich m.a.w. als een kwa- dratische functie: T (n) = n2. Wanneer de invoer met één groter wordt gemaakt dan duurt het algo- ritme dubbel zo lang: T (n) = 2n. Dit is een exponentiële uitvoerings- tijd. We kunnen de invoer dubbel zo groot maken en toch duurt het al- goritme maar een constante tijd langer: T (n) = log(n). Dit is een logaritmische uitvoeringstijd.... Bij de analyse van de zoekalgoritmen zien we dat de asymptotische uit- voeringstijd bepaald wordt door het aantal vergelijkingen dat wordt uitge- voerd. Aantal vergelijkingen bij sequentieel zoeken Bij sequentieel zoeken kunnen we ons afvragen hoeveel keer de vergelijking rij[i ] ̸= zoekItem op regel 3 van Algoritme 1.1 wordt uitgevoerd. In het beste geval staat het gezochte element helemaal vooraan de array en is er één zo’n vergelijking nodig. In het slechtste geval behoort het gezochte element niet tot de array. In dit geval wordt het element vergeleken met alle elementen van de array alvorens te besluiten dat het niet tot de array behoort. Dit zijn m.a.w. n vergelijkingen. Wanneer het element wel tot de array behoort dan zal het gemiddeld gezien ergens in het midden staan, zodat we verwachten ongeveer n/2 vergelijkingen uit te voeren. We zien m.a.w. dat het aantal vergelijkingen (en ook de uitvoeringstijd) in het slechtste geval ongeveer verdubbelt wanneer de lengte van de invoerrij wordt verdubbeld. De tijdscomplexiteit is lineair of van de orde n. We noteren dit als T (n) = O(n). Opmerking 1.7 Bij de complexiteitsanalyse, en meer bepaald bij het ge- bruik van de “Big-Oh” notatie, wiskundig genoteerd als O , wordt uitgegaan van het slechtst mogelijke geval om de uitvoeringstijd te beschrijven. Classic Computer Science Algorithms 16/09/2024 10 Hoofdstuk 1. Zoeken en Sorteren Aantal vergelijkingen bij binair zoeken Bij binair zoeken tellen we hoeveel keer de vergelijking rij[m] < zoekItem (1.1) op regel 6 in Algoritme 1.2 wordt uitgevoerd. Voor de eenvoud van de analyse nemen we aan dat de lengte van de rij een macht van twee is, of anders gezegd n = 2k , waarbij k een natuurlijk getal is. Wanneer k = 0, dan is de lengte van de rij gelijk aan 1 en wordt de vergelij- king hierboven geen enkele keer uitgevoerd1. Wanneer k = 1, dan is l = 0 en r = 1 bij de start van het algoritme en dus wordt m = 0. Als de vergelijking (1.1) evalueert naar true, dan wordt l = 1 en r = 1, in het andere geval wordt l = 0 en r = 0. In beide gevallen zal de hoofdlus van het algoritme stoppen. De vergelijking (1.1) wordt m.a.w. precies één keer uitgevoerd. Wanneer k = 2, dan is l = 0 en r = 3 bij de start van het algoritme. De eerste maal dat m wordt berekend krijgt deze m.a.w. de waarde m = 1. Wanneer de vergelijking (1.1) evalueert naar true dan zoeken we verder in de rechterhelft met l = 2 en r = 3, in het andere geval zoeken we verder in de linkerhelft met l = 0 en r = 1. In beide gevallen is de lengte van de deelrij waarin wordt gezocht gelijk aan 2. Het aantal bijkomende uitvoeringen van vergelijking (1.1) is dan, zoals reeds vastgesteld, gelijk aan 1. In dit geval zijn er m.a.w. precies twee uitvoeringen van vergelijking (1.1). Wanneer k = 3 (m.a.w. de lengte van de rij is 8) dan zal na de eerste uitvoe- ring van vergelijking (1.1) de lengte van de deelrij gereduceerd worden tot 4. In dit geval zijn er dus 1 + 2 = 3 uitvoeringen van de vergelijking (1.1). Op deze manier zien we dat wanneer n = 2k er precies k uitvoeringen zullen zijn van de vergelijking (1.1). Het verband tussen k en n wordt gegeven door n = 2k ⇐⇒ k = log2 (n). Dit betekent dat de uitvoeringstijd in dit geval logaritmisch groeit:
T (n) = O log2 (n). (1.2) 1 Er wordt wel een vergelijking uitgevoerd ná de lus om te verifiëren of het element gevonden werd maar deze vergelijking wordt steeds uitgevoerd en is onafhankelijk van de lengte van de rij. Classic Computer Science Algorithms 16/09/2024 11 Hoofdstuk 1. Zoeken en Sorteren Opmerking 1.8 (Willekeurige n) De redenering die we hierboven hebben gemaakt is enkel geldig wanneer n = 2k. Wat als de lengte van de rij niet precies een macht van twee is? In dit geval is het resultaat (1.2) nog steeds geldig. Stel bv. dat je wil zoeken in een rij van lengte 20. In gedachten kan je de rij uitbreiden tot een rij van lengte 32 (i.e. de volgende macht van 2). Dan zie je dat er voor de rij van lengte 20 hoogstens 5 vergelijkingen nodig zijn. Een experiment om de uitvoeringstijd te meten We voeren een experiment uit waarbij we de uitvoeringstijd van de algorit- men effectief meten. Dit gaat als volgt: Laat k de waardes 1 t.e.m. 14 doorlopen. Genereer een willekeurige rij van lengte n = 2k bestaande uit gehele getallen. Kies 30 random getallen uit deze rij. Voer voor elk van deze 30 random getallen de methode ZOEK S EQUEN - TIEEL en ZOEK B INAIR 100 000 keer uit en sla de uitvoeringstijd hiervan (apart) op. Anders gezegd, na het uitvoeren van het experiment beschikken we voor elk algoritme en voor elke gekozen waarde van n over 30 meetpunten die elk het gevolg zijn van het 100 000 keer uitvoeren van een methode-aanroep. Theoretisch verwachten we voor de methode ZOEK S EQUENTIEEL een line- aire uitvoeringstijd. In Figuur 1.1 tonen we in de linkerfiguur de rechte (door de oorsprong) die het beste2 past bij de gemiddelde uitvoeringstijd van deze methode. Voor de methode ZOEK B INAIR verwachten we daarentegen een logaritmi- sche uitvoeringstijd. In Figuur 1.1 tonen we in de rechterfiguur de best pas- sende logaritmische curve. Merk op dat de getallen op de verticale as van beide figuren van een volledig andere grootteorde zijn. 2 In het opleidingsonderdeel “Data Science & AI” zal duidelijk worden wat hiermee wordt bedoeld. Classic Computer Science Algorithms 16/09/2024 12 Hoofdstuk 1. Zoeken en Sorteren Figuur 1.1: Uitvoeringstijd van lineair en binair zoeken, resp. in de linker- en rechterfiguur. Merk op dat de getallen op de verticale as van beide figuren van een volledig andere grootteorde zijn. Merk ook op dat voor kleine waarden van n de uitvoeringstijden van de twee methoden niet significant van elkaar verschillen. Het verschil in ge- drag manifesteert zich wanneer de rijen waarin moet gezocht worden iets langer zijn. Dit zie je in Tabel 1.1. Verder merken we ook op dat de uitvoeringstijden van het algoritme van binair zoeken (voor een bepaalde waarde van n) zeer gelijkaardig zijn, on- afhankelijk van het element dat wordt gezocht. Bij lineair zoeken zien we hier een grote variatie optreden, omdat lineair zoeken snel werkt wanneer het element zich vooraan in de rij bevindt en veel trager wanneer het ele- ment achter in de rij aanwezig is3. 1.2 Sorteren van een Array In de vorige sectie hebben we gezien dat het doorzoeken van een array veel efficiënter verloopt wanneer deze gesorteerd is. In deze sectie bekijken we een drietal algoritmen om arrays te sorteren. Twee daarvan worden ge- zien als “eenvoudige” sorteeralgoritmen. Het derde algoritme is iets minder voor de hand liggend, maar heeft een betere uitvoeringstijd. 3 Inhet experiment werden geen testen gedaan met elementen die niet tot de array behoren. Bij zo’n experiment zullen de tijden voor binair zoeken zeer gelijkaardig blijven, terwijl voor lineair zoeken de tijden steeds aan de “grote” kant zullen liggen. Classic Computer Science Algorithms 16/09/2024 13 Hoofdstuk 1. Zoeken en Sorteren Lineair Zoeken Binair Zoeken n gemiddeld min max gemiddeld min max 2 0.023358 0.018782 0.028282 0.029508 0.027960 0.031835 4 0.030451 0.018702 0.044360 0.037046 0.034434 0.040373 8 0.045468 0.018790 0.064200 0.044859 0.041557 0.047688 16 0.070344 0.026154 0.111211 0.053811 0.051925 0.056694 32 0.116735 0.020733 0.226672 0.064633 0.060644 0.076644 64 0.161129 0.032630 0.372710 0.072495 0.068330 0.080041 128 0.439917 0.044428 0.746537 0.082789 0.076771 0.090164 256 0.706593 0.025980 1.438627 0.092677 0.085994 0.100332 512 1.686027 0.045711 3.502422 0.116800 0.101439 0.155817 1024 2.701336 0.211092 6.528466 0.136210 0.106221 0.289722 2048 6.096840 0.076119 13.212105 0.137714 0.121224 0.158811 4096 13.239109 0.221343 26.576251 0.153950 0.134502 0.163726 8192 26.328758 0.377525 51.927700 0.162872 0.149109 0.232349 16384 51.839257 5.057787 106.330041 0.175556 0.163862 0.269275 Tabel 1.1: Enkele uitvoeringstijden van lineair en binair zoeken. Per zoekmethode ziet men het gemiddelde, minimum en maximum van 30 tijdsmetingen. Elke tijdsmeting (aangeduid in seconden) bestaat op zijn beurt uit 100 000 herhalingen van dezelfde methodeoproep. 1.2.1 Sorteren door Selectie Het basisidee van sorteren door selectie kan eenvoudig samengevat wor- den: 1. Zoek het grootste element en plaats het achteraan. 2. Sorteer de rest van de array. We bekijken dit nu in iets meer detail. In de te sorteren array a gaan we op zoek naar het grootste element. In- dien dit element niet achteraan staat in de rij, moet dit element verwisseld worden met het element op de laatste plaats. Het grootste element staat nu achteraan in de rij; dat is de juiste plaats voor dit element. De (n − 1) overige elementen van de array moeten nog gesorteerd worden. Voor de deelrij a,... , a[n − 2] gaan we op analoge manier tewerk. Het grootste element in de rij wordt bepaald en achteraan geplaatst, dus op de Classic Computer Science Algorithms 16/09/2024 14 Hoofdstuk 1. Zoeken en Sorteren (n − 2)-de positie. Deze werkwijze wordt herhaald op steeds kortere deelrijen. De laatste keer zal de deelrij nog bestaan uit twee elementen. De implementatie wordt ge- geven in Algoritme 1.4. Algoritme 1.4 Sorteren door selectie. Invoer De array a is gevuld met n elementen. Uitvoer De array a is gesorteerd. 1: function SELECTION S ORT(a) 2: for i = n − 1... 1 by − 1 do ▷ achteraan starten 3: positie ← i 4: max ← a[i ] 5: for j = i − 1... 0 by − 1 do ▷ j doorloopt de deelrij 6: if a[ j] > max then 7: positie ← j 8: max ← a[ j] 9: end if 10: end for 11: a[positie] ← a[i ] ▷ grootste element wisselen met laatste 12: a[i ] ← max 13: end for 14: end function Voorbeeld 1.9 We passen het algoritme toe op een kleine voorbeeldrij. Het onderstreepte element is steeds het grootste element van het (mogelijks) nog niet gesorteerde deel van de array. Het deel achter de verticale streep is met zekerheid al correct. In elke iteratie groeit dit deel totdat finaal de volledige rij gesorteerd is. 44 55 12 42 94 18 06 67 44 55 12 42 67 18 06 |94 44 55 12 42 06 18 |67 94 44 18 12 42 06 |55 67 94 06 18 12 42 |44 55 67 94 06 18 12 |42 44 55 67 94 06 12 |18 42 44 55 67 94 06 12 18 42 44 55 67 94 Classic Computer Science Algorithms 16/09/2024 15 Hoofdstuk 1. Zoeken en Sorteren Complexiteitsanalyse De uitvoeringstijd wordt bepaald door het aantal keer dat de vergelijking a[ j] > max op regel 6 uitgevoerd wordt. Dit aantal komt overeen met het aantal keer dat de teller j van waarde wij- zigt. voor i wordt j aantal vergelijkingen n − 1 n − 2, n − 3,... , 1, 0 n−1 n − 2 n − 3, n − 4,... , 1, 0 n−2...... 1 0 1 n −1 n ( n − 1) totaal ∑k= 2 k =1 n ( n −1) De tabel geeft duidelijk weer dat de binnenste lus 2 keer wordt her- haald. Hieruit mogen we besluiten dat T (n) = O(n2 ). In de volgende paragrafen tonen we aan dat n −1 n ( n − 1) ∑ k = 1 + 2 + · · · + ( n − 2) + ( n − 1) = 2. k =1 Opmerking 1.10 (Een belangrijke som) Om de tijdscomplexiteit van sorte- ren door selectie te bepalen hebben we gebruikgemaakt van de volgende eigenschap: ( n + 1) n 1 + 2 + · · · + ( n − 1) + n =. (1.3) 2 Dit kan eenvoudig op de volgende manier worden aangetoond, bv. voor n = 10. Noteer alle getallen van 1 t.e.m. 10 van klein naar groot en daar- onder nog eens van groot naar klein. Neem nu de som van de getallen die onder elkaar staan. Deze som is steeds gelijk aan 11. Hoeveel keer hebben we nu een 11 staan? Dat is 10 keer. De som van alle getallen 11 is m.a.w. 110. Dit is echter niet het finale antwoord want we hebben elk getal van 1 Classic Computer Science Algorithms 16/09/2024 16 Hoofdstuk 1. Zoeken en Sorteren t.e.m. 10 nu twee keer geteld, één keer in de bovenste rij en nog een keer in de onderste rij. De finale som is bijgevolg 110/2 = 55. Dit proces wordt geïllustreerd in de onderstaande tabel. stijgend 1 2 3 4 5 6 7 8 9 10 omgekeerd 10 9 8 7 6 5 4 3 2 1 som 11 11 11 11 11 11 11 11 11 11 Je kan dit proces uiteraard veralgemenen om zo het bewijs te vinden voor formule (1.3). Dit bewijs zou volgens de overlevering door de wiskundige Gauss reeds in de basisschool zijn ontdekt, al is het niet zeker dat dit verhaal ooit effectief gebeurd is4. De uitvoeringstijd van sorteren door selectie wordt bepaald door de waarde van de som: 1 + 2 + · · · + ( n − 2) + ( n − 1). (1.4) We tonen nu een manier om de waarde van deze som te bepalen uit verge- lijking (1.3). Het eerste wat we ons moeten realiseren is dat we in vergelij- king (1.3) ook een andere letter mogen gebruiken dan n in zowel het linker- als rechterlid. Laat ons bv. eens de letter m gebruiken: ( m + 1) m 1 + 2 + · · · + ( m − 1) + m =. (1.5) 2 Als we nu het linkerlid hiervan vergelijken met uitdrukking (1.4) dan zien we dat deze overeenkomen als we voor m de uitdrukking (n − 1) invullen5. M.a.w. als we in het rechterlid van (1.5) de letter m vervangen door (n − 1) dan krijgen we de uitkomst van (1.4). Als we deze vervanging uitvoeren dan krijgen we:
( m + 1) m ( n − 1) + 1 ( n − 1) n ( n − 1) ⇝ =. 2 2 2 Dit is precies wat we wilden aantonen. 4 https://nl.wikipedia.org/wiki/Carl_Friedrich_Gauss#Anekdotes 5 Bij deze vervanging voeg je voor de veiligheid best haakjes toe rond n − 1, vandaar dat we schrijven (n − 1). Classic Computer Science Algorithms 16/09/2024 17 Hoofdstuk 1. Zoeken en Sorteren Opmerking 1.11 (Een tweede belangrijke som) Een tweede som die nut- tig zal zijn in deze cursus is de som van een aantal termen die afkomstig zijn uit een meetkundige (geometrische) rij: a n +1 − 1 1 + a + a 2 + · · · + a n −1 + a n =. (1.6) a−1 In het linkerlid is de verhouding van twee opeenvolgende termen constant: a k +1 = a. ak De formule (1.6) kan eenvoudig bewezen worden. Stel S n = 1 + a + a 2 + · · · + a n −1 + a n , (1.7) dan zoeken we een gesloten formule voor Sn. Hiertoe vermenigvuldigen we Sn met a: aSn = a + a2 + · · · + an + an+1. (1.8) Als we nu (1.7) aftrekken van (1.8), dan krijgen we: aSn − Sn = a + a2 + · · · + an + an+1
− 1 + a + a 2 + · · · + a n −1 + a n
= an+1 − 1. Alle termen a t.e.m. an komen immers twee keer voor in het recherlid, één keer met een plusteken en één keer met een minteken. Op die manier zijn het enkel de termen an+1 en 1 die overblijven in het rechterlid. Deze laatste vergelijking kan herschreven worden als: ( a − 1)Sn = an+1 − 1, wat equivalent is met de formule (1.6). 1.2.2 Sorteren door Tussenvoegen Het basisidee achter sorteren door tussenvoegen kan als volgt samengevat worden: 1. Veronderstel dat er reeds een deel vooraan de array gesorteerd is. Classic Computer Science Algorithms 16/09/2024 18 Hoofdstuk 1. Zoeken en Sorteren 2. Neem het eerste element van het niet gesorteerde deel en voeg dit ele- ment toe op de juiste plaats in het gesorteerde deel. Op deze manier wordt het gesorteerde deel uitgebreid. Sorteren door tussenvoegen of “card sort“ kan m.a.w. het best vergeleken worden met het op volgorde steken van kaarten. We beginnen met de tweede kaart. We kijken of deze voor de eerste moet komen of niet. Vervolgens nemen we de volgende kaart en deze plaatsen we dan direct op de juiste positie ten opzichte van de vorige kaarten. Zo doen we verder tot alle kaarten op de juiste plaats zitten. In het algoritme is dit: indien de eerste i elementen reeds gesorteerd zijn dan gaan we kijken naar het (i + 1)-ste element. Dit element wordt op de juiste plaats tussengevoegd. Indien nodig moeten de reeds gesorteerde grotere elementen allen één positie doorschuiven. Voorbeeld 1.12 We passen dit principe nu toe op een eenvoudige rij. De verticale streep geeft aan welk deel van de array reeds is gesorteerd. In het bijzonder zijn de getallen voor de verticale streep steeds gesorteerd. Het onderstreepte getal is hetgene we gaan invoegen in het gesorteerde deel. 44| 55 12 42 94 18 06 67 44 55| 12 42 94 18 06 67 12 44 55| 42 94 18 06 67 12 42 44 55| 94 18 06 67 12 42 44 55 94| 18 06 67 12 18 42 44 55 94| 06 67 06 12 18 42 44 55 94| 67 06 12 18 42 44 55 67 94 In Algoritme 1.5 vindt men de pseudocode voor sorteren door tussenvoe- gen. Complexiteitsanalyse Anders dan bij sorteren door selectie hangt de uitvoeringstijd van het algo- ritme in dit geval niet enkel af van de inputgrootte. Ook de manier waarop de elementen bij aanvang geordend zijn speelt een rol. Classic Computer Science Algorithms 16/09/2024 19 Hoofdstuk 1. Zoeken en Sorteren Algoritme 1.5 Sorteren door tussenvoegen. Invoer De array a is gevuld met n elementen. Uitvoer De array a is gesorteerd. 1: function CARD S ORT(a) 2: for i = 1... n − 1 do 3: x ← a [i ] ▷ x bevat het in te voegen element 4: j←i ▷ j zoekt de juiste positie voor x 5: while j > 0 and x < a[ j − 1] do ▷ schuif grotere elementen op 6: a [ j ] ← a [ j − 1] ▷ schuif a[ j − 1] eentje op 7: j ← j−1 8: end while 9: a[ j] ← x ▷ x wordt op de juiste positie tussengevoegd 10: end for 11: end function Indien de rij bij aanvang in omgekeerde volgorde gesorteerd is, zullen de n ( n −1) opdrachten in de binnenste lus 2 keer uitgevoerd worden. Elke indi- viduele uitvoering van zo’n opdracht neemt constante tijd. Het zonet ge- noemde aantal is het maximum aantal keer dat de lus kan doorlopen wor- den. Dit komt overeen met een uitvoeringstijd T (n) = O(n2 ), (het slechtste geval). Als de rij bij aanvang van het algoritme reeds gesorteerd is, zal het stopcrite- rium voor de binnenste lus steeds voldaan zijn waardoor de lus niet wordt uitgevoerd. De buitenste lus wordt (n − 1) keer uitgevoerd. Dit resulteert in een lineaire uitvoeringstijd. Men kan bewijzen dat ook in het gemiddelde geval, voor een willekeurige ordening van de inputrij, geldt dat het aantal vergelijkingen groeit zoals n2. In het gemiddelde geval heeft sorteren door tussenvoegen dus, net als sorteren door selectie, een kwadratische uitvoeringstijd. Omdat bij complexiteitsanalyse, zoals reeds eerder vermeld, steeds wordt uitgegaan van het slechtst mogelijke scenario kunnen we besluiten dat de tijdscomplexiteit van sorteren door tussenvoegen kwadratisch is: T (n) = O(n2 ). Classic Computer Science Algorithms 16/09/2024 20 Hoofdstuk 1. Zoeken en Sorteren 1.2.3 Sorteren door Samenvoegen Sorteren door samenvoegen (mergesort6 ) is een ingewikkelder algoritme dan de voorgaande twee eenvoudige sorteeralgoritmes maar is ook een heel stuk efficiënter. Het basisidee is het volgende: 1. Sorteer de eerste helft van de array. 2. Sorteer de tweede helft van de array. 3. Voeg de twee gesorteerde deelrijen samen tot één gesorteerde array. De eerste twee stappen in dit proces gebeuren op een recursieve manier. Voorbeeld 1.13 Beschouw de rij 44 55 12 42 94 18 06 67. Deze wordt opgesplitst in twee deelrijen 44 55 12 42 94 18 06 67. Beide deelrijen worden vervolgens recursief gesorteerd tot 12 42 44 55 06 18 67 94. Tot slot worden de gesorteerde deelrijen samengevoegd tot de gesorteerde rij 06 12 18 42 44 55 67 94. We bekijken nu in iets meer detail hoe het samenvoegen van twee gesor- teerde deelrijen precies verloopt. Voor het samenvoegen of mergen van de deelrijen wordt een hulprij aangemaakt. In deze hulprij worden de beide deelrijen samengevoegd. 6 In het boek “Algoritmen en Datastructuren” van Niklaus Wirth (de bedenker van de Pascal-programmeertaal) wordt dit als “sorteren door mengen” vertaald. Classic Computer Science Algorithms 16/09/2024 21 Hoofdstuk 1. Zoeken en Sorteren Voor het samenvoegen van de deelrijen wordt in de beide deelrijen links ge- start. Dit is voor beide deelrijen bij het kleinste element. Deze twee elemen- ten worden vergeleken, het kleinste van de twee wordt opgeslagen in de hulprij. Zowel voor de beide deelrijen als voor de hulprij wordt er een teller geïnitialiseerd die de huidige positie in die rij bijhoudt. Wanneer een ele- ment uit een deelrij is opgeslagen in de hulprij mag de teller van deze deelrij een positie opschuiven net als de teller van de hulprij. Dit proces wordt her- haald tot één van de deelrijen volledig is doorlopen. Vervolgens kunnen de resterende elementen van de andere deelrij achteraan toegevoegd worden in de hulprij. Voorbeeld 1.14 (Samenvoegen van twee gesorteerde (deel)rijen) Het sa- menvoegen van twee deelrijen wordt stap voor stap uitgewerkt in het vol- gende voorbeeld. De eerste twee kolommen geven de respectievelijke ge- sorteerde (deel)rijen weer. Het getal in het vetjes is het element waarnaar op dat moment wordt verwezen. De derde kolom geeft de hulprij weer: deze wordt bij elke iteratie met één element uitgebreid. Dit getal is steeds het kleinste van de twee getallen waarnaar op dat moment wordt verwezen in de gesorteerde (deel)rijen. In dit voorbeeld werd de eerste deelrij als eerste volledig gekopieerd naar de hulprij. Alle resterende getallen uit de tweede deelrij worden dan gekopi- eerd (zonder verdere controles) naar de hulprij. Dit gebeurt op de onderste lijn in onderstaande tabel. 12 42 44 55 06 18 67 94 06 12 42 44 55 06 18 67 94 06 12 12 42 44 55 06 18 67 94 06 12 18 12 42 44 55 06 18 67 94 06 12 18 42 12 42 44 55 06 18 67 94 06 12 18 42 44 12 42 44 55 06 18 67 94 06 12 18 42 44 55 12 42 44 55 06 18 67 94 06 12 18 42 44 55 67 94 Algoritme 1.6 beschrijft de methode MERGE S ORT. Door de recursie zullen we opnieuw gebruik moeten maken van een hulpmethode waarin de eigen- lijke recursie plaatsvindt. De functie MERGE S ORT roept de recursieve functie MERGE S ORT R ECURSIVE aan. Deze functie wordt uitgewerkt in Algoritme 1.7. In deze methode Classic Computer Science Algorithms 16/09/2024 22 Hoofdstuk 1. Zoeken en Sorteren Algoritme 1.6 De hoofdmethode voor sorteren door samenvoegen. Invoer de array a is gevuld met n elementen. Uitvoer de array a is gesorteerd 1: function MERGE S ORT(a) 2: MERGE S ORT R ECURSIVE ( a, 0, n − 1) 3: end function wordt een deel van de rij gesorteerd door het te sorteren deel op te split- sen in twee deelrijen van halve lengte. Vervolgens worden de gesorteerde deelrijen samengevoegd. Het samenvoegen van de beide deelrijen gebeurt in de functie MERGE. Deze functie wordt beschreven in Algoritme 1.8. Algoritme 1.7 Het algoritme mergeSortRecursive sorteert een deel van de array a. Invoer de array a is gevuld met n elementen, begin en einde wijzen naar geldige posities in de array a. Uitvoer de elementen met index begin tot en met index einde werden gesor- teerd. 1: function MERGE S ORT R ECURSIVE(( a, begin, einde) 2: if begin < einde then 3: midden ← ⌊(begin + einde)/2)⌋ 4: MERGE S ORT R ECURSIVE ( a, begin, midden) 5: MERGE S ORT R ECURSIVE ( a, midden + 1, einde) 6: MERGE ( a, begin, midden, einde) 7: end if 8: end function Complexiteitsanalyse We starten met een analyse van de functie om twee deelrijen van lengte n/2 samen te voegen tot een gesorteerde rij van lengte n. In de methode MERGE wordt elk element van de twee halve deelrijen één keer gekopieerd naar de hulprij, en vervolgens wordt elk element nog eens teruggekopieerd naar zijn uiteindelijke plaats in de array a. Per kopieerbewerking gebeurt er een hoeveelheid werk dat niet afhangt van de lengte van array a. Dit betekent dat de tijdscomplexiteit van de methode MERGE lineair is. Als de samen te voegen deelrijen dubbel zo lang worden, dan zal de uitvoeringstijd (onge- veer) verdubbelen. Voor de eenvoud (en omdat constante factoren in het algemeen toch niet van belang zijn wanneer men algoritmische complexi- Classic Computer Science Algorithms 16/09/2024 23 Hoofdstuk 1. Zoeken en Sorteren Algoritme 1.8 De methode M ERGE voegt twee gesorteerde deelrijen samen. Invoer de array a is gevuld met n elementen; de elementen van de deelrij gaande van de begin-positie tot en met de midden-positie zijn gesorteerd; de elementen van de deelrij gaande van de (midden+1)-positie tot en met de eind-positie zijn gesorteerd. Uitvoer de elementen met index begin t.e.m. index einde werden gesorteerd. 1: function M ERGE(a, begin, midden, einde) 2: i ← begin ▷ de teller i doorloopt de linkse deelrij 3: j ← midden + 1 ▷ de teller j doorloopt de rechtse deelrij 4: k←i ▷ de teller k doorloopt de hulparray hulpa 5: hulpa ← nieuwe array[n] ▷ tijdelijke hulpopslag 6: while i ≤ midden and j ≤ einde do ▷ totdat een deelrij leeg is 7: if a[i ] ≤ a[ j] then ▷ het kleinste element komt eerst 8: hulpa[k ] ← a[i ] 9: i ← i+1 10: else 11: hulpa[k ] ← a[ j] 12: j ← j+1 13: end if 14: k ← k+1 ▷ er is een element in hulpa opgeslagen 15: end while 16: if i > midden then ▷ de 2de deelrij moet leeggemaakt worden 17: while j ≤ einde do 18: hulpa[k ] ← a[ j] 19: j ← j+1 20: k ← k+1 21: end while 22: else ▷ de 1ste deelrij moet leeggemaakt worden 23: while i ≤ midden do 24: hulpa[k ] ← a[i ] 25: i ← i+1 26: k ← k+1 27: end while 28: end if 29: for k = begin... einde do ▷ kopieer gesorteerde deelrij naar a 30: a[k ] ← hulpa[k ] 31: end for 32: end function Classic Computer Science Algorithms 16/09/2024 24 Hoofdstuk 1. Zoeken en Sorteren teit bestudeert vanuit het standpunt van asymptotische analyse) stellen we deze hoeveelheid werk voor door n. Hoeveel werk zal sorteren door samenvoegen verzetten? We berekenen dit nu (voor de eenvoud) voor rijen waarvan de lengte een macht van 2 is, m.a.w. n = 2k waarbij k een natuurlijk getal voorstelt. Als de lengte van de rij gelijk is aan 1 dan is T (1) = 1, want er moet enkel gecontroleerd worden dat de lengte van de rij gelijk is aan 1. Wanneer de lengte van de rij gelijk is aan 2, dan is de totale hoeveelheid werk T (2) = T (1) + T (1) + 2, want we moeten de linkerdeelrij sorteren (eerste term T (1)), we moeten de rechterdeelrij sorteren (tweede term T (1)) en tenslotte moeten de twee ge- sorteerde deelrijen worden samengevoegd (term 2). Samen geeft dit T (2) = 2T (1) + 2 = 2 × 1 + 2 = 4. Voor een rij van lengte 4 = 22 wordt dit op een gelijkaardige manier: T (4) = 2T (2) + 4 = 2 × 4 + 4 = 12, en voor een rij van lengte 8 = 23 krijgen we: T (8) = 2T (4) + 8 = 2 × 12 + 8 = 32. Welk patroon kunnen we hierin herkennen? Merk op dat T (1) = T (20 ) = 1 = 1 × (0 + 1) T (2) = T (21 ) = 4 = 2 × (1 + 1) T (4) = T (22 ) = 12 = 4 × (2 + 1) T (8) = T (23 ) = 32 = 8 × (3 + 1) Hieruit kunnen we herkennen dat het algemene patroon is: T ( n ) = T (2k ) = n × ( k + 1 ). Hieruit kunnen we besluiten dat de tijdscomplexiteit T (n) van sorteren door samenvoegen wordt gegeven door:
T (n) = O n log2 (n). Classic Computer Science Algorithms 16/09/2024 25 Hoofdstuk 1. Zoeken en Sorteren Opmerking 1.15 (Geheugengebruik) Hoewel mergesort op het niveau van de uitvoeringstijd efficiënter is dan de voorgaande methodes, is deze me- thode minder efficiënt op het niveau van de benodigde geheugenruimte. Het MERGE-algoritme maakt immers gebruik van een extra array hulpa waar- in de gesorteerde rij tijdelijk wordt opgeslagen. Dit komt de geheugencom- plexiteit niet ten goede. 1.3 Oefeningen 1. Ga in de array (1 2 3 4 6 7 8 9 10) achtereenvolgens op zoek naar de waarden 3, 5 en 10. Maak hierbij gebruik van het algoritme ZOEK - B INAIR. Houd tijdens je simulatie de waarden bij van de variabelen l, r en m. 2. (Dodona) Implementeer de iteratieve methode voor binair zoeken. 3. (Dodona) Herwerk en implementeer de oplossingsmethode voor sor- teren door selectie zodat niet langer het grootste element naar achteren wordt gebracht maar het kleinste element naar voor. Het reeds gesor- teerde deel van de array bevindt zich m.a.w. steeds vooraan. 4. Pas de oplossingsmethode beschreven in het opgegeven algoritme aan zodat de elementen niet langer van klein naar groot worden gesor- teerd maar van groot naar klein. a) sorteren door tussenvoegen b) sorteren door mengen 5. (Dodona) Bubble sort is een oplossingsmethode voor het sorteren van een array a van lengte n. Algoritme 1.9 beschrijft deze methode in pseudo-code. a) Implementeer deze methode in Python. b) Tel het exact aantal keer, in functie van n, dat de controle van regel 4, nl. a[ j − 1] > a[ j] wordt uitgevoerd. Gebruik een gesloten formule om je resultaat weer te geven. Leid hieruit de O -notatie voor de uitvoeringstijd van het algoritme bubbleSort af. c) Stel a = (13, 7, 8, 1). Volg in een overzichtelijke tabel de uitwer- king van BUBBLE S ORT(a). Noteer in de tabel minstens de ver- schillende waarden die i, j en a doorlopen. Classic Computer Science Algorithms 16/09/2024 26 Hoofdstuk 1. Zoeken en Sorteren Algoritme 1.9 De methode bubbleSort. Invoer De array a is gevuld met n elementen. Uitvoer De array a is gesorteerd. 1: function BUBBLE S ORT(a) 2: for i = 0... n − 2 do 3: for j = n − 1... i + 1 by − 1 do 4: if a[ j − 1] > a[ j] then 5: wissel de elementen a[ j − 1] en a[ j] 6: end if 7: end for 8: end for 9: end function 6. Hieronder volgen een aantal codefragmenten f i. Bepaal voor elk van deze fragmenten de waarde van x in functie van de invoerwaarde n. Leid hieruit de asymptotische uitvoeringstijd, t.t.z. de O -notatie, af van deze verschillende codefragmenten. Je kan bij je berekeningen ge- bruik maken van de reeds geziene belangrijke sommen uit de theorie, en van deze eigenschap7 : n n(n + 1)(2n + 1) ∑ i2 = 6 , i =1 Tracht je resultaten experimenteel te verifiëren door een programma te schrijven dat de verhouding berekent van de f i (n) over je theoretisch voorspelde uitvoeringstijd. Wanneer je de juiste uitvoeringstijd hebt dan zou deze verhouding zo goed als constant moeten zijn (voor grote waarden van n). a) 1: function S OM 1(n) 2: x←0 3: for i = 1... n do 4: x ← x+1 5: end for 6: return (x) 7: end function b) 1: function S OM 2(n) 2: x←0 3: for i = 1... 2n do 7 Gebruik bv. Wolfram Alpha om dit aan te tonen Classic Computer Science Algorithms 16/09/2024 27 Hoofdstuk 1. Zoeken en Sorteren 4: for j = 1... n do 5: x ← x+1 6: end for 7: end for 8: return (x) 9: end function c) 1: function S OM 3(n) 2: x←0 3: for i = 1... n do 4: for j = 1... i do 5: for k = 1... j do 6: x ← x+1 7: end for 8: end for 9: end for 10: return (x) 11: end function d) 1: function S OM 4(n) 2: x←0 3: for i = 1... n do 4: for j = 1... i do 5: for k = 1... i do 6: x ← x+1 7: end for 8: end for 9: end for 10: return (x) 11: end function e) 1: function S OM 5(n) 2: x←0 3: i←n 4: while i ≥ 1 do 5: x ← x+1 6: i ← ⌊i/2⌋ 7: end while 8: return (x) 9: end function f) 1: function S OM 6(n) Classic Computer Science Algorithms 16/09/2024 28 Hoofdstuk 1. Zoeken en Sorteren 2: x←0 3: i←n 4: while i ≥ 1 do 5: for j = 1... i do 6: x ← x+1 7: end for 8: i ← ⌊i/2⌋ 9: end while 10: return (x) 11: end function g) 1: function S OM 7(n) 2: x←0 3: i←n 4: while i ≥ 1 do 5: for j = 1... n do 6: x ← x+1 7: end for 8: i ← ⌊i/2⌋ 9: end while 10: return (x) 11: end function Classic Computer Science Algorithms 16/09/2024  H OOFDSTUK 2 Gelinkte lijsten De elementen van een array bezetten steeds opeenvolgende ge- heugenplaatsen wat ervoor zorgt dat men de elementen kan aan- spreken in constante tijd. Anderzijds zorgt dit ervoor dat het min- der eenvoudig is om elementen ergens “in het midden” toe te voegen. G ELINKTE LIJSTEN zijn een voorbeeld van een dynami- sche datastructuur waarbij de samenhang tussen de verschillende componenten gerealiseerd wordt door wijzers (pointers) naar de elementen in de datastructuur waardoor toevoegen “in het mid- den” eenvoudiger wordt. We bestuderen ENKELVOUDIG en DUB - BEL GELINKTE LIJSTEN. We gebruiken de gelinkte lijsten om een STAPEL te realiseren en we zien enkele problemen die gemakkelijk met een stapel kunnen opgelost worden. In de oefeningen zien we tenslotte ook hoe een WACHTRIJ kan gerealiseerd worden m.b.v. een gelinkte lijst. Bij sorteren door tussenvoegen hebben we gezien dat wanneer we een ele- ment willen tussenvoegen op een bepaalde plaats in de array dat we dan alle achterliggende elementen één plaats moeten opschuiven. Het is een- voudig in te zien dat dit eveneens het geval is wanneer we een element willen verwijderen uit een array. Dit zorgt ervoor dat dit soort bewerkingen in een array in het slechtste geval een lineaire tijdscomplexiteit hebben: alle elementen moeten immers worden verplaatst. We bekijken nu een nieuwe datastructuur, nl. een lineair gelinkte lijst of kortweg gelinkte lijst, waarbij dit probleem wordt opgelost. Het voordeel van een gelinkte lijst is dat het uitvoeren van een basisfunctie Classic Computer Science Algorithms 16/09/2024 30 Hoofdstuk 2. Gelinkte lijsten zoals toevoegen of verwijderen van elementen in een constante tijd gebeurt, op voorwaarde dat men reeds weet waar het element moet worden toege- voegd of verwijderd. Het opzoeken van een element in een gelinkte lijst vraagt echter nog steeds een lineaire tijd. Een tweede voordeel van een gelinkte lijst is dat deze a priori geen be- perking oplegt aan het aantal elementen dat aan de lijst kan toegevoegd worden. Gaandeweg wordt de lijst verder uitgebreid, een gelinkte lijst is m.a.w. een dynamische structuur. 2.1 Specificatie Een gelinkte lijst bestaat uit een aantal knopen die via een kettingstructuur aan elkaar geschakeld zijn. Een knoop bestaat uit twee velden: een data-veld data waarin de eigenlijke data wordt opgeslagen; een veld volgende dat verwijst naar de volgende knoop in de lijst. De laatste knoop bevat een wijzer null; op figuren wordt die aangeduid met een schuine streep. Voor de eerste knoop moet een referentie eerste bijgehouden worden. In een lege lijst is de referentie eerste gelijk aan null. Figuur 2.1 illustreert deze structuur. De belangrijkste basisbewerkingen voor een enkelvoudig gelinkte lijst zijn: zoek( ): zoekt de positie van de knoop met als data-veld het argument; verwijder( ): verwijdert de knoop die volgt na de opgegeven knoop en geeft de waarde van het data-veld van de verwijderde knoop weer; voegToe( ): voegt een knoop toe na een opgegeven knoop, het data- veld krijgt de waarde van het argument. Classic Computer Science Algorithms 16/09/2024 31 Hoofdstuk 2. Gelinkte lijsten Figuur 2.1: Een enkelvoudig gelinkte lijst. 2.2 Implementatie van een Gelinkte Lijst Een gelinkte lijst wordt voorgesteld door een ketting van aaneengescha- kelde knopen. Elke knoop bevat een data-veld data en een veld volgende dat de referentie naar de volgende knoop van de lijst bijhoudt. De referentie eerste verwijst naar de eerste knoop van de lijst. De referentie null geeft aan dat het einde van de gelinkte lijst bereikt is. We starten met een implementatie voor een knoop. 2.2.1 Implementatie van een Knoop We schrijven de klasse Knoop in UML-notatie. De constructor wordt in pseudocode beschreven. De klasse Knoop in UML Knoop - data : Element - volgende : Knoop + Knoop( ) De gedefinieerde Knoop is een datastructuur die een element van een niet nader gedefinieerde klasse Element bevat. Classic Computer Science Algorithms 16/09/2024 32 Hoofdstuk 2. Gelinkte lijsten Algoritme voor de constructor De constructor Knoop maakt een nieuw object van de klasse Knoop aan. Algoritme 2.1 De constructor. Invoer / Uitvoer er werd een nieuwe knoop aangemaakt 1: function K NOOP 2: data ← null 3: volgende ← null 4: end function 2.2.2 Implementatie van een gelinkte lijst De klasse Knoop wordt als inwendige klasse (inner class) van de klasse Ge- linkteLijst geïmplementeerd. Dit betekent dat methodes van de klasse Ge- linkteLijst toegang hebben tot de velden van Knoop. We schrijven de klasse GelinkteLijst uit in UML-notatie. Alle methodes wor- den in pseudocode beschreven. De klasse GelinkteLijst in UML GelinkteLijst - eerste : Knoop + GelinkteLijst( ) + zoek(x: Element) : Knoop + verwijder(ref : Knoop) : Element + voegToe(ref : Knoop, x: Element) : / Algoritme voor de constructor De constructor GelinkteLijst maakt een nieuw object van de klasse Gelinkte- Lijst aan. Deze methode wordt in Algoritme 2.2 beschreven in pseudocode. Algoritme voor het opzoeken van een element x Het opzoeken van een knoop met dataveld x in een gelinkte lijst l gebeurt door de knopen van de lijst één voor één te overlopen. Classic Computer Science Algorithms 16/09/2024 33 Hoofdstuk 2. Gelinkte lijsten Algoritme 2.2 De constructor van een lineair gelinkte lijst. Invoer / Uitvoer er werd een nieuwe (lege) gelinkte lijst aangemaakt 1: function G ELINKTE L IJST 2: eerste ← null 3: end function Als eerste knoop wordt de knoop waar de referentie eerste naar verwijst bekeken. Indien de waarde van het dataveld van deze knoop niet overeen- stemt met x wordt de volgende knoop bekeken. Deze knoop is eenvoudig te vinden door de ketting te volgen via het referentieveld. Dit proces wordt herhaald tot x wordt gevonden of het einde van de gelinkte lijst wordt be- reikt. Het eerste voorkomen van het element x wordt bijgehouden. De referentie naar de knoop met dataveld x wordt geretourneerd. Deze methode wordt in Algoritme 2.3 beschreven in pseudocode. Algoritme 2.3 Een element x opzoeken in een gelinkte lijst. De return- waarde is een instantie van een Knoop. Invoer de gelinkte lijst werd aangemaakt, x is het te zoeken element Uitvoer de referentie naar de eerste knoop met dataveld gelijk aan x werd geretourneerd, indien x niet voorkomt in de lijst werd de referentie null geretourneerd. 1: function ZOEK(x) 2: ref ← eerste 3: while ref ̸= null and ref.data ̸= x do 4: ref ← ref.volgende 5: end while 6: return ref 7: end function De uitvoeringstijd voor de methode zoek is afhankelijk van de positie van x in de lijst. In het slechtste geval wordt elke knoop van de lijst overlopen en wordt x helemaal niet gevonden. Dit komt overeen met een lineaire uitvoe- ringstijd. Classic Computer Science Algorithms 16/09/2024 34 Hoofdstuk 2. Gelinkte lijsten In het beste geval vindt men de gezochte referentie onmiddellijk. Dit komt overeen met een constante uitvoeringstijd. In het gemiddelde geval moet ongeveer de helft van de knopen over- lopen worden. Dit komt opnieuw overeen met een lineaire uitvoe- ringstijd. Het zoeken van een element x in een gelinkte lijst gebeurt niet efficiënter dan in een gewone array. Integendeel, in de praktijk is het volgen van refe- renties (pointers) trager dan het doorlopen van een array. De overige basisfuncties voor een gelinkte lijst zullen wel allemaal uitvoer- baar zijn in een constante tijd, op voorwaarde dat de referentie reeds gekend is. Algoritme voor het verwijderen van een knoop De functie VERWIJDER verwacht als inputwaarde een referentie ref. Deze referentie ref verwijst naar de knoop in de gelinkte lijst die de te verwijde- ren knoop voorafgaat. De waarde van het data-veld van de verwijderde knoop wordt geretourneerd. De reden dat we de voorafgaande knoop moe- ten meegeven is omdat de referentie naar de volgende dient aangepast te worden in de knoop voorafgaand aan de te verwijderen knoop. Er is echter geen efficiënte manier om in een lineair gelinkte lijst de voorganger van een knoop te vinden. De methode VERWIJDER wordt geïllustreerd in Figuur 2.2. Algoritme 2.4 beschrijft de methode VERWIJDER in pseudocode. Algoritme 2.4 De knoop na de gegeven knoop verwijderen in een gelinkte lijst l. Invoer de gelinkte lijst l bestaat, de knoop ref is niet de laatste knoop in de lijst. Uitvoer de knoop die volgt na de knoop met referentie ref werd verwijderd uit de lijst, het data-veld van de verwijderde knoop werd geretourneerd. 1: function VERWIJDER(ref) 2: x ← ref.volgende.data 3: ref.volgende ← ref.volgende.volgende 4: return x 5: end function Classic Computer Science Algorithms 16/09/2024 35 Hoofdstuk 2. Gelinkte lijsten Figuur 2.2: Verwijderen van de knoop na de gegeven knoop. Opmerking 2.1 (Vooraan verwijderen) Aangezien de methode verwijder de knoop verwijdert die volgt ná de knoop die wordt aangewezen door de ge- geven referentie, is het niet mogelijk de eerste knoop van de gelinkte lijst te verwijderen m.b.v. deze methode. Dit probleem wordt aangepakt in Para- graaf 2.2.3. Algoritme voor het toevoegen van een knoop De methode VOEG T OE voegt een nieuwe knoop met data-veld x toe na de knoop die wordt aangeduid door een gegeven referentie ref. De werkwijze wordt geïllustreerd in Figuur 2.3 en omvat de volgende stap- pen: creëer een nieuwe knoop hulp; stockeer de waarde x in het data-veld van de knoop hulp; laat hulp.volgende verwijzen naar ref.volgende; laat ref.volgende verwijzen naar hulp. De vertaling van deze werkwijze naar pseudocode wordt gegeven in Algo- ritme 2.5. Classic Computer Science Algorithms 16/09/2024 36 Hoofdstuk 2. Gelinkte lijsten Figuur 2.3: Toevoegen van een knoop na de gegeven knoop. Algoritme 2.5 Een knoop met dataveld x toevoegen na de gegeven knoop. Invoer de gelinkte lijst bestaat, en ref is niet null. Uitvoer na de knoop, waarnaar gerefereerd wordt door de referentie ref , werd een nieuwe knoop met data-veld x toegevoegd. 1: function VOEG T OE(ref, x) 2: hulp ← nieuwe Knoop( ) 3: hulp.data ← x 4: hulp.volgende ← ref.volgende 5: ref.volgende ← hulp 6: end function Opmerking 2.2 (Vooraan toevoegen) De methode VOEG T OE laat enkel toe een knoop toe te voegen ná de knoop die wordt aangewezen door de gege- ven referentie. Deze methode laat niet toe een knoop toe te voegen helemaal vooraan in de gelinkte lijst. Eveneens is het met deze methode niet mogelijk om een knoop toe te voegen aan een lege gelinkte lijst. Dit kan verholpen worden door gebruik te maken van een ankercomponent. 2.2.3 Het gebruik van ankercomponenten De methoden VERWIJDER en VOEG T OE uit de voorgaande paragraaf zijn en- kel bruikbaar voor algemene gevallen. Het speciale geval om een element toe te voegen aan een lege lijst of een element toe te voegen vooraan in de Classic Computer Science Algorithms 16/09/2024 37 Hoofdstuk 2. Gelinkte lijsten lijst is niet mogelijk met de besproken methode.1 Het is eveneens niet moge- lijk het eerste element van een gelinkte lijst te verwijderen met de methode VERWIJDER volgens de besproken specificatie. Een eenvoudige en elegante oplossing voor deze bijzondere gevallen is om een ankercomponent toe te voegen aan de gelinkte lijst. De ankercomponent is een extra knoop die helemaal vooraan aan de gelinkte lijst wordt toege- voegd. Het data-veld van deze ankercomponent is leeg. Het referentie-veld van de ankercomponent verwijst naar de eerste knoop van de gelinkte lijst. De ankercomponent maakt dus logisch gezien geen deel uit van de eigen- lijke lijst maar dient enkel om de implementatie te vereenvoudigen. Figuur 2.4 is een illustratie van een gelinkte lijst met ankercomponent. Figuur 2.4: Een gelinkte lijst met ankercomponent. Door deze ankercomponent toe te voegen heeft elke knoop een voorganger in de lijst. Dit betekent dat nu ook de eerste knoop kan verwijderd worden of dat op de eerste positie een nieuwe knoop kan toegevoegd worden. Een lege gelinkte lijst bestaat nu uit één enkele knoop, nl. de ankercompo- nent, en de referentie naar deze component. Figuur 2.5 is een voorstelling van een lege gelinkte lijst wanneer een ankercomponent wordt gebruikt. Het gebruik van een ankercomponent vereenvoudigt de basisbewerkingen voor een gelinkte lijst. Er moet immers niet steeds op bijzondere situaties gecontroleerd worden. 1 Dit betekent dat het eigenlijk niet mogelijk is om deze implementatie effectief aan de praat te krijgen aangezien het niet mogelijk is om een knoop toe te voegen aan een lege lijst! Classic Computer Science Algorithms 16/09/2024 38 Hoofdstuk 2. Gelinkte lijsten Figuur 2.5: Een lege gelinkte lijst met gebruik van een ankercomponent. 2.3 Dubbelgelinkte lijsten In een enkelvoudig gelinkte lijst is de eerste knoop van de lijst vlot bereik- baar. De laatste knoop bereiken kost echter tijd lineair in de lengte van de lijst. Een mogelijke oplossing hiervoor is om in elke knoop van de gelinkte lijst twee referenties bij te houden: een referentie volgende en een referentie vo- rige. Naast de referentie eerste naar de eerste knoop in de lijst, is het dan logisch om ook een referentie laatste naar de laatste knoop in de lijst bij te houden. Een dergelijke structuur wordt een dubbelgelinkte lijst genoemd. Figuur 2.6 is een illustratie van een dergelijke lijst. Figuur 2.6: Een dubbelgelinkte lijst met twee ankercomponenten. In een dubbelgelinkte lijst wordt meestal gewerkt met twee ankercompo- Classic Computer Science Algorithms 16/09/2024 39 Hoofdstuk 2. Gelinkte lijsten nenten. Figuur 2.7 stelt een lege dubbelgelinkte lijst voor. Figuur 2.7: Een lege dubbelgelinkte lijst met twee ankercomponenten. Testen of de lijst leeg is, kan als volgt: als eerste.volgende = laatste of als laat- ste.vorige = eerste. 2.4 Beschrijving en Implementatie van Stapels 2.4.1 Beschrijving van een Stapel De naam stapel of stack is gekozen naar analogie met een stapel boeken. Indien we een boek van de stapel nodig hebben dan is het best bereikbare boek hetgeen bovenaan ligt. Een boek dat zich op een andere plaats bevindt, is slechts bereikbaar als we alle bovenliggende boeken verwijderd hebben. Ditzelfde principe wordt toegepast voor het datatype stack: Een element dat we willen toevoegen aan een stapel, komt steeds bo- venop de reeds bestaande stapel te liggen. Enkel het bovenste element van de stapel kan verwijderd worden. Dit element wordt de top van de stapel genoemd. Een stapel is m.a.w. een LIFO- of Last-In-First-Out-structuur. De voorgaande beschrijving legt de structuur van een stapel vast. Voor de implementatie van deze structuur zullen we gebruik maken van een klasse Stack. In deze klasse worden een aantal basisbewerkingen gedefinieerd. Deze zijn: Classic Computer Science Algorithms 16/09/2024 40 Hoofdstuk 2. Gelinkte lijsten Stack( ): constructor, maakt een nieuwe stapel aan waarna de stapel bestaat als lege stapel; empty( ): controleert of een stapel al dan niet leeg is; push( ): voegt een nieuw element toe bovenaan een stapel, het toege- voegde element wordt de nieuwe top van de stapel; pop( ): verwijdert het bovenste element van een stapel en retourneert het verwijderde element; peek( ): geeft het bovenste element van de stapel terug, zonder het te verwijderen. De omschrijvingen van deze bewerkingen moeten vertaald worden naar al- goritmen die hun werking ondubbelzinnig vastleggen. Indien de imple- mentatie efficiënt gebeurt zal de uitvoeringstijd van de algoritmen niet af- hankelijk zijn van de grootte van de stapel. 2.4.2 Implementatie van een Stapel We tonen nu hoe een stapel kan geïmplementeerd worden als een gelinkte lijst waarbij enkel de top bereikbaar is. In het bijzonder wordt een stapel geïmplementeerd door een referentie t naar de eerste knoop in de lijst, die de top van de stapel bevat. Figuur 2.8 is een illustratie van een stapel geïmplementeerd als gelinkte lijst. De klasse Stack in UML Stack - t : Knoop + Stack( ) + empty( ) : boolean + push(x: Element) : / + pop( ) : Element + peek( ) : Element De klasse Knoop wordt als inwendige klasse (inner class) van de klasse Stack geïmplementeerd. Dit betekent dat methodes van de klasse Stack toe- Classic Computer Science Algorithms 16/09/2024 41 Hoofdstuk 2. Gelinkte lijsten Figuur 2.8: Een stapel geïmplementeerd als gelinkte lijst. Het gebruik van een ankercomponent is hier niet nodig. De top van de stapel bevat het element A. Het element Q werd als eerste element op de stapel geplaatst. gang hebben tot de velden van Knoop. De implementatie van de klasse Knoop is zoals voorheen. De constructor Een lege stapel bevat nog geen elementen, m.a.w. de referentie t is null. Algoritme 2.6 De constructor. Invoer / Uitvoer er werd een nieuwe stapel aangemaakt, deze stapel bestaat als lege stapel. 1: function S TACK 2: t ← null 3: end function Algoritme ter controle of een stapel al dan niet leeg is De methode EMPTY controleert of een stapel al dan niet leeg is. Het resultaat van de methode is een boolean. Algoritme 2.7 beschrijft deze methode. Het enige wat er gebeurt is nagaan of de referentie naar de top al dan niet gelijk is aan null. Classic Computer Science Algorithms 16/09/2024 42 Hoofdstuk 2. Gelinkte lijsten Algoritme 2.7 Controleren of een stapel s al dan niet leeg is. Invoer de stapel s bestaat Uitvoer de waarde true of false werd afgeleverd, afhankelijk van het feit of de stapel s leeg is of niet. 1: function EMPTY 2: return t = null 3: end function Algoritme voor het toevoegen van een element aan een stapel De methode PUSH wordt geïllustreerd in Figuur 2.9. Figuur 2.9: Een element toevoegen aan de top van de stapel. Het element x wordt bovenop de stapel geduwd. Algoritme 2.8 beschrijft de methode PUSH in pseudocode. Algoritme 2.8 Een element x toevoegen aan de top van een stapel s. Invoer de stapel s bestaat, x moet op de stapel worden geplaatst Uitvoer het element x werd als top-element op de stapel s geplaatst. 1: function PUSH(x) 2: hulp ← nieuwe Knoop( ) 3: hulp.data ← x 4: hulp.volgende ← t 5: t ← hulp 6: end function Classic Computer Science Algorithms 16/09/2024 43 Hoofdstuk 2. Gelinkte lijsten Algoritme voor het verwijderen van een element van een stapel In dit algoritme wordt de top van de stapel verwijderd en geretourneerd. Er wordt verondersteld dat de stapel niet leeg is. De methode POP wordt ge- ïllustreerd in Figuur 2.10 en Algoritme 2.9 beschrijft deze methode in pseu- docode. Figuur 2.10: De top van de stapel verwijderen. Algoritme 2.9 De top verwijderen en de waarde ervan retourneren. Invoer de stapel s bestaat en is niet leeg Uitvoer de top werd verwijderd en de waarde van de top werd geretour- neerd. 1: function POP 2: x ← t.data 3: t ← t.volgende 4: return x 5: end function Algoritme voor het retourneren van de waarde van de top van een stapel Er wordt opnieuw verondersteld dat de stapel niet leeg is. Algoritme 2.10 De waarde van de top retourneren. Invoer de stapel s bestaat en is niet leeg Uitvoer de waarde van de top werd geretourneerd, s werd niet gewijzigd. 1: function PEEK 2: return t.data 3: end function Classic Computer Science Algorithms 16/09/2024 44 Hoofdstuk 2. Gelinkte lijsten 2.5 Toepassingen van Stapels 2.5.1 Controleren van haakjes Elke programmeur kent het verschijnsel dat een programma niet werkt om- dat ergens een haakje ontbreekt. Compilers controleren steeds of de haakjes allemaal correct zijn en genereren een foutboodschap wanneer dit niet het geval is. Basisidee Voor de controle van de haakjes worden twee zaken onderzocht: 1. Er wordt gecontroleerd of elk openend haakje juist één overeenkom- stig sluitend haakje heeft, bv. voor elk ‘(’-symbool moeten we verder in het programma één ‘)’-symbool terugvinden. Andere mogelijke kop- pels zijn: [ en ], { en }. M.a.w. de symbolen moeten in paren voorko- men. 2. De volgorderegels moeten in acht genomen worden. De haakjes mo- gen genest zijn, dit wil zeggen dat een paar haakjes zich tussen een ander paar mag bevinden, maar paren haakjes mogen elkaar niet over- lappen. Bijvoorbeeld, ([ ]) is een geldige volgorde van symbolen, terwijl ([ )] niet geldig is. We willen met behulp van een stapel een algoritme ontwerpen dat de ver- effening van symbolen verifieert. Dit kan als volgt: Maak een lege stapel aan. Doorloop alle symbolen één voor één. Indien het symbool een haakje is, moet er een opdracht uitgevoerd worden: – als het een open-symbool is, plaats het dan op de stapel (push- bewerking); – als het een sluit-symbool is onderscheiden we twee mogelijke si- tuaties: Classic Computer Science Algorithms 16/09/2024 45 Hoofdstuk 2. Gelinkte lijsten * de stapel is leeg: er wordt een foutmelding gegenereerd aan- gezien er geen corresponderend open-symbool aan is vooraf gegaan; * de stapel is niet leeg: het top-element wordt er afgehaald (pop-bewerking). Dit symbool wordt vergeleken met het net ingelezen symbool, als beide symbolen niet corresponderen wordt een fout gemeld. Als alle karakters zijn ingelezen en de stapel is niet leeg, dan wordt een fout gemeld. Dit betekent immers dat er nog open-symbolen zijn waarvoor geen sluit-symbool is gevonden. Algoritme Algoritme 2.11 geeft pseudocode voor het controleren van de haakjes in een array van strings. De pseudocode om te controleren of het om een openend haakje gaat en om na te gaan of haakjes van dezelfde soort zijn wordt niet getoond omdat deze niet tot de essentie van het algoritme behoren. 2.5.2 Waardebepaling van een rekenkundige uitdrukking Binnen de wiskunde worden in een rekenkundige uitdrukking de binaire operatoren zoals + en × normaalgezien tussen de operanden geschreven. Bijvoorbeeld: 1 + 2 × 3. Hierbij staan de operatoren + en × tussen de operanden 1, 2 en 3. Een dergelijke notatie wordt een infix-notatie genoemd. In de meeste program- meertalen wordt deze notatie overgenomen. De rekenkundige uitdrukkingen in infix-notatie kunnen echter niet recht- streeks door de compiler naar machine-code vertaald worden. De postfix- notatie is beter geschikt voor de vertaling naar machine-code. De postfixnotatie staat ook bekend onder de benaming RPN (Reverse Polish Notation). Bij sommige modellen van zakrekenmachines wordt de post- fixnotatie gebruikt, bv. bij een aantal rekenmachines van het merk HP. In een postfix-uitdrukking worden de operatoren na hun operanden ge- schreven. Classic Computer Science Algorithms 16/09/2024 46 Hoofdstuk 2. Gelinkte lijsten Algoritme 2.11 Controle op correct gebruik van haakjes. Invoer uitdrukking is een array van Strings met de tokens van een uitdruk- king waarin eventueel haakjes voorkomen. Uitvoer indien alle open haakjes correct worden afgesloten werd er geen foutmelding gegenereerd. In het andere geval wordt er een boodschap getoond op het scherm 1: function CONTROLEER H AAKJES(uitdrukking) 2: s ← S TACK () 3: for i = 0... uitdrukking.lengte − 1 do 4: symbool ← uitdrukking[i ] 5: if symbool is openend haakje then 6: s.PUSH(symbool) 7: else 8: if symbool is sluitend haakje then 9: if s.EMPTY() then 10: P RINT("Te veel sluit symbolen") 11: else 12: voorgaand ← s.POP () 13: if symbool en voorgaand niet corresponderend then 14: P RINT( "Fout symbool:", symbool) 15: end if 16: end if 17: end if 18: end if 19: end for 20: if not s