MergeSort
Voor lijsten met veel elementen is MergeSort een zeer efficiënt algoritme. MergeSort maakt gebruik van de divide-and-conquermethode. In het Nederlands wordt dit ook wel de verdeel-en-heersmethode genoemd.
Soms is een probleem te groot om direct op te lossen. De divide-and-conquermethode splitst een probleem op in kleinere deelproblemen. Deze deelproblemen worden eerst opgelost. Daarna wordt de oplossing van alle deelproblemen samengevoegd tot de totaaloplossing van het probleem.
Deze aanpak is ook gebruikt bij het handig sorteren van de speelkaarten in paragraaf 1.1.2. Eerst werden de kaarten over meerdere stapels verdeeld (de verdeelfase). Daarna werden ze samengevoegd (de verzamelfase).
Een docent heeft van twee klassen de antwoorden van een toets. Per klas zijn de antwoorden gesorteerd op alfabetische volgorde van de achternaam van de leerlingen. De docent wil deze twee stapels samenvoegen tot één stapel. Hij hoeft dan niet helemaal opnieuw te beginnen met sorteren. Het makkelijkst is als hij een derde stapel maakt. Hierbij kijkt hij steeds naar de eerste twee stapels. Het exemplaar met de alfabetisch opvolgende naam legt hij op de nieuwe stapel. Als de twee stapels 'op' zijn, is de derde stapel correct op alfabet gesorteerd.
De divide-and-conquermethode bestaat dus uit drie stappen:
- Divide: verdeel het probleem in kleinere deelproblemen.
- Conquer: los de deelproblemen op. Lukt dat niet? Verdeel de deelproblemen dan in nog kleinere deelproblemen.
- Combine: voeg de oplossingen van de deelproblemen samen.
Maak jouw eigen website met JouwWeb