De viktigaste algoritmerna och datastrukturerna som du verkligen behöver känna till
Om du vill bli programvaruingenjör, men inte vet var du ska börja, ska vi bespara dig spänningen: det är algoritmer och datastrukturer.
När du väl har fått grepp om dessa grundpelare i programmeringen kommer du att börja se dem överallt. Och ju fler algoritmer och datastrukturer du lär dig, desto mer kommer de att fungera som jetbränsle för din karriär som programvaruingenjör.
För att komma igång ska vi först göra en djupdykning i Sök och Sortera, två klasser av algoritmer som du inte kan leva utan. Sedan gör vi en snabb genomgång av resten av landskapet som omfattar träd, grafer, dynamisk programmering och massor av annat.
Helt grovt sett finns det två kategorier av sökalgoritmer som du behöver känna till direkt: linjära och binära. Depth First Search (DFS) och Breadth First Search (BFS) är också superviktiga, men vi sparar dem till avsnittet om graftraversering nedan.
Linjär sökning
De linjära och binära algoritmerna heter så för att beskriva hur lång tid (tidskomplexitet) en sökning kommer att ta baserat på storleken på den indata som ska sökas.
Till exempel, med linjära sökalgoritmer, om du har 100 objekt att söka så skulle det i värsta fall krävas att du tittar på varje objekt i inmatningen innan du kommer fram till ditt önskade värde. Den kallas linjär eftersom den tid det tar att söka är exakt korrelerad med antalet objekt i sökningen (100 objekt/input = 100 kontroller/komplexitet)
Kort sagt, linjär = enkel (det finns inget smart med algoritmen). Ett exempel: Tänk dig att du försöker hitta din vän Lin bland en rad människor som står i ingen särskild ordning. Du vet redan hur Lin ser ut, så du behöver helt enkelt titta på varje person, en efter en, i tur och ordning, tills du känner igen eller inte känner igen Lin. Så är det. När du gör detta följer du den linjära sökalgoritmen
Binär sökning
Binär sökning har fått sitt namn eftersom ordet binär betyder ”av eller relaterat till 2 saker” och algoritmen fungerar genom att dela upp inmatningen i två delar tills den hittar det objekt som söks. Den ena halvan innehåller det sökta objektet och den andra halvan inte. Processen fortsätter tills den plats där inmatningen delas upp blir det objekt som söks. Binär sökning är i princip bara ett mycket disciplinerat tillvägagångssätt för elimineringsprocessen. Det är snabbare än linjär sökning, men det fungerar bara med ordnade sekvenser.
Ett exempel bör göra detta tydligare. Anta att du försöker hitta din vän Bin (som är 1,75 m) i en enda rad av personer som har ordnats efter längd från vänster till höger, från kortast till högst. Det är en riktigt lång kö, och du har inte tid att gå igenom hela kön en och en och jämföra allas längd med Bins. Vad kan du göra?
Gör binärsökning. Du väljer en person i mitten av kön och mäter dennes längd. De är 1,75 meter. Så direkt vet du att den här personen, tillsammans med alla till höger om dem, inte är Bin. Nu när du har halverat ditt problem vänder du din uppmärksamhet mot resten av kön och väljer personen i mitten igen. De är 1,75 meter långa. Så du kan utesluta den personen och alla till vänster om dem, vilket återigen halverar problemet. Och så vidare. Efter bara fem eller sex sådana här uppdelningar kan du snabbt hitta Bin på en bråkdel av den tid det tog dig att hitta Lin. Därmed har du följt den binära sökalgoritmen.
Sortering
Sortering, även kallad sortering, av listor med objekt är en av de vanligaste programmeringsuppgifterna du kommer att göra som utvecklare. Här tittar vi på två av de mest användbara sorteringsalgoritmerna: MergeSort och QuickSort.
MergeSort
Antag att du i stället för att stöta på den ordnade raden av personer i exemplet ovan behöver skapa en ordnad rad av personer ur en oordnad grupp. Du har inte mycket tid, så du kommer på en strategi för att påskynda saker och ting.
Du låter först gruppen av människor, som alla är samlade, dela sig i två delar. Sedan låter du var och en av de två grupperna dela sig i två igen, och så vidare, tills du helt och hållet har att göra med individer. Du börjar sedan para ihop individerna och låter den högsta av de två i varje par stå till höger om den andra. Ganska snart är alla organiserade i dessa ordnade vänster-höger-par.
Nästan börjar man slå ihop de ordnade paren till ordnade grupper om fyra, sedan slår man ihop de ordnade grupperna om fyra till ordnade grupper om åtta, och så vidare. Till slut upptäcker du att du har en komplett, höjdordnad rad av människor, precis som den du stötte på ovan. Utan att veta om det har du följt algoritmen MergeSort för att åstadkomma din bedrift.
QuickSort
QuickSort är lite för komplext för att man lätt ska kunna föreställa sig det hos människor, så låt oss komma lite närmare koden. Till att börja med kan vi tänka oss att du har en oordnad lista, eller array, med åtta nummer som du vill ordna.
4 2 13 6 15 12 7 9
Du skulle kunna använda MergeSort, men du har hört att QuickSort generellt sett är snabbare, så du bestämmer dig för att pröva det. Ditt första steg är att välja ett nummer i listan som kallas pivot. Att välja rätt pivotnummer gör hela skillnaden för hur snabbt QuickSort fungerar, och det finns färdiga formler att följa för att välja bra pivotnummer. Men för tillfället håller vi det enkelt och väljer bara det sista numret i matrisen som vårt pivotnummer: 9.
4 2 13 6 15 12 7 9
För att göra nästa steg lättare att följa skapar vi en separator i början av matrisen och representerar den med pundetecknet.
# 4 2 13 6 15 12 7 9
Om vi rör oss från vänster till höger genom vår matris är vårt mål att placera alla tal som är mindre än pivoten (9) till vänster om separatorn och alla tal som är större än (eller lika med) pivoten till höger om separatorn. Vi börjar med det första numret i vår matris: 4. För att flytta det till vänster om separatorn flyttar vi bara upp separatorn ett element:
4 # 2 13 6 15 12 7 9
Vi gör samma sak med nästa tal: 2.
4 2 # 13 6 15 12 7 9
Men sedan kommer vi till 13, som är större än pivottalet 9 och redan står till höger om separatorn. Så vi lämnar det i fred. Därefter kommer vi till 6, som måste gå till vänster om separatorn. Så först byter vi den mot 13 för att få den på plats:
4 2 # 6 13 15 12 7 9
Därefter flyttar vi separatorn förbi den:
4 2 6 # 13 15 12 7 9
Nästa nummer är 15, som redan är till höger om separatorn, så vi låter det vara. Sedan har vi 12. Samma sak. Men 7, vår sista siffra innan vi når pivot, behöver samma typ av hjälp att förflytta sig som 6 gjorde. Så vi byter ut 7 mot 13 för att få det på plats:
4 2 6 # 7 15 12 13 9
Därefter flyttar vi återigen separatorn förbi det:
4 2 6 7 # 15 12 13 9
Slutligt kommer vi till vårt pivotnummer: 9. Enligt samma logik som ovan byter vi ut 15 mot 9 för att få pivotnumret där det ska vara:
4 2 6 7 # 9 12 13 15
Då alla nummer till vänster om 9 nu är mindre än 9, och alla nummer till höger om 9 är större än 9, är vi klara med vår första cykel av QuickSort. Därefter behandlar vi varje uppsättning av fyra nummer på vardera sidan av separatorn som en ny array att tillämpa QuickSort på. Vi ska bespara dig detaljerna, men nästa omgång kommer att ge oss fyra sifferpar som vi enkelt kan tillämpa vår sista omgång av QuickSort på. Slutresultatet blir följande ordnade lista som tog oss mindre tid att generera än vad den skulle ha gjort med den enklare MergeSort:
2 4 6 7 9 12 13 15
Sorteringsalgoritmer som fusklapp
Detta är de vanligaste sorteringsalgoritmerna med några rekommendationer för när de ska användas. Internalisera dessa! De används överallt!
Heap sort: När du inte behöver en stabil sortering och du bryr dig mer om prestanda i värsta fall än i genomsnitt. Den är garanterat O(N log N) och använder O(1) hjälputrymme, vilket innebär att du inte oväntat kommer att få slut på heap- eller stackutrymme vid mycket stora indata.
Introsort: Detta är en snabbsortering som byter till en heap-sortering efter ett visst rekursionsdjup för att komma runt snabbsorteringens O(N²) värsta fall. Det är nästan alltid bättre än en vanlig snabbsortering, eftersom du får det genomsnittliga fallet av en snabbsortering med garanterad O(N log N)-prestanda. Det enda skälet till att använda en heap-sortering i stället för detta är förmodligen i system med mycket begränsat minne där O(log N) stackutrymme är praktiskt taget betydande.
Insertionssortering: När N garanterat är litet, bland annat som grundfall för snabbsortering eller sammanslagningssortering. Även om detta är O(N²) har det en mycket liten konstant och är en stabil sortering.
Bubble sort, selection sort: När du gör något snabbt och smutsigt och av någon anledning inte bara kan använda standardbibliotekets sorteringsalgoritm. Den enda fördelen dessa har jämfört med insertion sort är att de är något lättare att implementera.
Snabbsortering: När du inte behöver en stabil sortering och när genomsnittlig prestanda är viktigare än värsta prestanda. En snabbsortering är O(N log N) i genomsnitt och O(N²) i värsta fall. Ett bra genomförande använder O(log N) extra lagringsutrymme i form av stapelutrymme för rekursion.
Merge sort: När du behöver en stabil O(N log N)-sortering är detta ditt enda alternativ. De enda nackdelarna med den är att den använder O(N) hjälputrymme och har en något större konstant än en snabbsortering. Det finns några sammanslagningar på plats, men AFAIK är de alla antingen inte stabila eller sämre än O(N log N). Till och med O(N log N) in place sorterna har en så mycket större konstant än den gamla vanliga sammanslagningssorteringen att de är mer teoretiska kuriositeter än användbara algoritmer.