Top algoritmen en datastructuren die je echt moet kennen

Als je software-ingenieur wilt worden, maar niet weet waar je moet beginnen, zullen we je de spanning besparen: het zijn algoritmen en gegevensstructuren.

Als je eenmaal de essentie van deze pijlers van het programmeren doorhebt, zul je ze overal gaan tegenkomen. En hoe meer algoritmen en gegevensstructuren je leert, hoe meer ze zullen dienen als brandstof voor je carrière als software-engineer.

Om je op weg te helpen, nemen we eerst een diepe duik in Search en Sort, twee klassen algoritmen waar je niet zonder kunt. Daarna een kort overzicht van de rest van het landschap, waaronder bomen, grafieken, dynamisch programmeren en nog veel meer.

Ruwweg zijn er twee categorieën zoekalgoritmen die je meteen moet kennen: lineaire en binaire. Depth First Search (DFS) en Breadth First Search (BFS) zijn ook super-belangrijk, maar die bewaren we voor de graph traversal sectie hieronder.

Lineair zoeken

De lineaire en binaire algoritmen worden zo genoemd om te beschrijven hoe lang (tijdcomplexiteit) een zoekactie gaat duren op basis van de grootte van de invoer waarnaar gezocht wordt.

Bij lineaire zoekalgoritmen bijvoorbeeld moet je in het ergste geval, als je 100 items moet doorzoeken, elk item in de invoer bekijken voordat je de gewenste waarde hebt gevonden. Het wordt lineair genoemd omdat de tijd die nodig is om te zoeken precies gecorreleerd is met het aantal items in de zoekopdracht (100 items/invoer =100 controles/complexiteit)

In het kort, lineair = eenvoudig (er is niets slims aan het algoritme). Bijvoorbeeld: stel je voor dat je probeert je vriend Lin te vinden tussen een rij mensen die in willekeurige volgorde staan. Je weet al hoe Lin eruit ziet, dus je hoeft alleen maar naar elke persoon te kijken, een voor een, in volgorde, totdat je Lin herkent of niet. Dat is het. Daarmee volgt u het lineaire zoekalgoritme

Binaire zoekactie

Binaire zoekactie dankt haar naam aan het woord binair dat “van of betrekking hebbend op 2 dingen” betekent en het algoritme werkt door de invoer in twee delen op te splitsen totdat het gezochte item is gevonden. De ene helft bevat het gezochte item en de andere helft niet. Dit proces gaat door totdat de plaats waar de invoer is gesplitst, het gezochte item wordt. Binair zoeken is in feite gewoon een zeer gedisciplineerde benadering van het eliminatieproces. Het is sneller dan lineair zoeken, maar het werkt alleen met geordende reeksen.

Een voorbeeld zal dit duidelijker maken. Stel, je probeert je vriend Bin (die 1,80 m is) te vinden in een rij mensen die van links naar rechts op lengte zijn gerangschikt, van kort naar lang. De rij is erg lang en je hebt geen tijd om alles één voor één te doorlopen en de lengte van iedereen te vergelijken met die van Bin. Wat kun je doen?

Binaire zoekactie. U selecteert de persoon in het midden van de rij en meet zijn lengte. Hij is 1,78 m. Je weet dus meteen dat deze persoon, samen met iedereen rechts van hem, geen Bin is. Nu je je probleem in tweeën hebt gedeeld, richt je je aandacht op de rest van de rij en kiest opnieuw de middelste persoon. Ze zijn 1,80 m. Dus kan je die persoon en iedereen links van hem uitsluiten, en het probleem opnieuw in twee snijden. En zo verder. Na vijf of zes van deze opsplitsingen heb je Bin snel gevonden in een fractie van de tijd die je nodig had om Lin te vinden.

Sorteren

Het ordenen, ook wel sorteren genoemd, van lijsten met items is een van de meest voorkomende programmeertaken die je als ontwikkelaar zult uitvoeren. Hier kijken we naar twee van de nuttigste sorteeralgoritmen: MergeSort en QuickSort.

MergeSort

Laten we eens veronderstellen dat je in plaats van de geordende rij mensen in het voorbeeld hierboven tegen te komen, een geordende rij mensen moet maken uit een ongeordende groep. Je hebt niet veel tijd, dus je bedenkt een strategie om de zaken te versnellen.

Je laat eerst de groep mensen, die allemaal ineengedoken zitten, in tweeën splitsen. Dan laat u elk van de twee groepen weer in tweeën splitsen, enzovoort, totdat u alleen nog maar met individuen te maken hebt. Dan begin je de individuen in paren te verdelen, en laat je de grootste van de twee in elk paar rechts van de andere staan. Al gauw is iedereen georganiseerd in deze links-rechts geordende paren.

Daarna voeg je de geordende paren samen tot geordende groepen van vier; vervolgens voeg je de geordende groepen van vier samen tot geordende groepen van acht; enzovoort. Uiteindelijk heb je een complete, in hoogte geordende rij mensen, precies zoals je hierboven hebt gezien. Zonder het te weten, heb je het MergeSort algoritme gevolgd om je prestatie te volbrengen.

QuickSort

QuickSort is een beetje te complex om je gemakkelijk voor te stellen aan mensen, dus laten we eens wat dichter bij de code komen. Om te beginnen, stel je voor dat je een ongeordende lijst, of array, van acht getallen hebt die je wilt ordenen.

4 2 13 6 15 12 7 9

Je zou MergeSort kunnen gebruiken, maar je hoort dat QuickSort over het algemeen sneller is, dus je besluit het te proberen. Je eerste stap is het kiezen van een getal in de lijst dat je de spil noemt. Het kiezen van het juiste pivot getal zal het verschil maken in hoe snel je QuickSort uitvoert, en er zijn kant-en-klare formules om te volgen voor het kiezen van goede pivots. Maar voor nu houden we het eenvoudig en nemen we het laatste getal in de matrix als spilnummer: 9.

4 2 13 6 15 12 7 9

Om de volgende stap makkelijker te volgen te maken, maken we een scheidingsteken aan het begin van de matrix en geven dat aan met het pond-teken.

# 4 2 13 6 15 12 7 9

Van links naar rechts door onze matrix, is ons doel elk getal kleiner dan de spil (9) links van het scheidingsteken te zetten, en elk getal groter dan (of gelijk aan) de spil rechts van het scheidingsteken. We beginnen met het eerste getal in onze matrix: 4. Om het naar links van het scheidingsteken te verplaatsen, schuiven we het scheidingsteken één element omhoog:

4 # 2 13 6 15 12 7 9

Hetzelfde doen we met het volgende getal: 2.

4 2 # 13 6 15 12 7 9

Maar dan komen we bij 13, dat groter is dan het spilgetal 9 en al aan de rechterkant van het scheidingsteken staat. Dus laten we het met rust. Dan komen we bij 6, dat links van het scheidingsteken moet komen te staan. Dus eerst verwisselen we het met 13 om het op zijn plaats te krijgen:

4 2 # 6 13 15 12 7 9

Dan verplaatsen we het scheidingsteken erlangs:

4 2 6 # 13 15 12 7 9

Daarna komt 15, dat al rechts van het scheidingsteken staat, dus we laten het met rust. Dan hebben we 12. Hetzelfde. Maar 7, ons laatste getal voordat we de spil bereiken, heeft dezelfde hulp nodig bij het verplaatsen als 6. Dus verwisselen we 7 met 13 om het in positie te krijgen:

4 2 6 # 7 15 12 13 9

Dan, nogmaals, verplaatsen we het scheidingsteken erlangs:

4 2 6 7 # 15 12 13 9

Eindigend komen we bij ons spilgetal: 9. Volgens dezelfde logica als hierboven verwisselen we 15 met 9 om het spilgetal te krijgen waar het moet zijn:

4 2 6 7 # 9 12 13 15

Omdat alle getallen links van 9 nu kleiner zijn dan 9, en alle getallen rechts van 9 groter zijn dan 9, zijn we klaar met onze eerste cyclus van QuickSort. Vervolgens behandelen we elke reeks van vier getallen aan weerszijden van het scheidingsteken als een nieuwe matrix waarop QuickSort wordt toegepast. We zullen u de details besparen, maar de volgende ronde zal ons vier paren getallen geven waarop we gemakkelijk onze laatste ronde van QuickSort kunnen toepassen. Het eindresultaat is de volgende geordende lijst die ons minder tijd kostte om te genereren dan met het eenvoudigere MergeSort:

2 4 6 7 9 12 13 15

Sorteeralgoritmen spiekbriefje

Dit zijn de meest voorkomende sorteeralgoritmen met enkele aanbevelingen voor wanneer je ze moet gebruiken. Leer deze kennen! Ze worden overal gebruikt!

Heap sort: Wanneer je geen stabiele sort nodig hebt en je meer geeft om worst case performance dan average case performance. Het is gegarandeerd O(N log N), en gebruikt O(1) hulpruimte, wat betekent dat je niet onverwachts heap- of stackruimte tekort komt bij zeer grote ingangen.

Introsort: Dit is een quick sort die na een bepaalde recursiediepte overschakelt op een heap sort om de O(N²) worst case van quick sort te omzeilen. Het is bijna altijd beter dan een gewone oude quick sort, omdat je het gemiddelde geval van een quick sort krijgt, met gegarandeerde O(N log N) prestaties. Waarschijnlijk is de enige reden om een heap sort te gebruiken in plaats van dit, in systemen met ernstige geheugenbeperkingen waar O(log N) stackruimte praktisch significant is.

Insertion sort: Wanneer N gegarandeerd klein is, ook als het basisgeval van een quick sort of merge sort. Hoewel dit O(N²) is, heeft het een zeer kleine constante en is het een stabiele sort.

Bubble sort, selection sort: Wanneer je iets snel en smerigs doet en om een of andere reden niet gewoon het sorteeralgoritme van de standaardbibliotheek kunt gebruiken. Het enige voordeel van deze sorts ten opzichte van insertion sort is dat ze iets eenvoudiger te implementeren zijn.

Quick sort: Wanneer je geen stabiele sort nodig hebt en average case performance belangrijker is dan worst case performance. Een quick sort is gemiddeld O(N log N), O(N²) in het slechtste geval. Een goede implementatie gebruikt O(log N) hulpopslag in de vorm van stackruimte voor recursie.

Merge sort: Als je een stabiele, O(N log N) sort nodig hebt, is dit ongeveer je enige optie. De enige nadelen zijn dat het O(N) hulpruimte gebruikt en een iets grotere constante heeft dan een quick sort. Er zijn enkele in-place merge sorts, maar AFAIK zijn ze allemaal of niet stabiel of slechter dan O(N log N). Zelfs de O(N log N) in-place sorts hebben zo’n veel grotere constante dan de gewone oude merge sort dat ze meer theoretische curiosa zijn dan bruikbare algoritmen.