Top algoritmusok és adatszerkezetek, amiket tényleg tudnod kell

Ha szoftvermérnök szeretnél lenni, de nem tudod, hol kezdd, megspóroljuk a feszültséget: az algoritmusok és adatszerkezetek.

Ha egyszer megérted a programozás ezen pilléreinek lényegét, mindenhol találkozni fogsz velük. És minél több algoritmust és adatszerkezetet tanulsz meg, annál inkább ezek szolgálnak majd a szoftvermérnöki karriered motorjaként.

Az induláshoz először merüljünk el mélyebben a Search és a Sort algoritmusok két olyan osztályába, amelyek nélkül nem tudsz élni. Ezután egy gyors áttekintést készítünk a többi területről, amelyek közé tartoznak a fák, a gráfok, a dinamikus programozás és még rengeteg más.

Gyakorlatilag a keresési algoritmusoknak két kategóriáját kell azonnal megismerned: a lineáris és a bináris algoritmusokat. A Depth First Search (DFS) és a Breadth First Search (BFS) szintén szuper fontosak, de ezeket meghagyjuk az alábbi gráftraverzális részre.

Lineáris keresés

A lineáris és bináris algoritmusok azért kapták ezt a nevet, hogy leírják, mennyi ideig (időbonyolultság) fog tartani a keresés a keresett bemenet mérete alapján.

A lineáris keresési algoritmusok esetében például, ha 100 elemet kell keresni, akkor a legrosszabb esetben a bemenet minden elemét meg kell nézni, mielőtt a kívánt értékre bukkanunk. Azért nevezik lineárisnak, mert a kereséshez szükséges idő pontosan korrelál a keresett elemek számával (100 elem/bemenet = 100 ellenőrzés/bonyolultság)

Röviden: lineáris = egyszerű (nincs semmi okos az algoritmusban). Például: képzeld el, hogy megpróbálod megtalálni Lin barátodat egy sorban álló emberek között, akik nem állnak különösebb sorrendben. Már tudod, hogy Lin hogy néz ki, így egyszerűen csak meg kell nézned minden egyes személyt, egyenként, sorban, amíg fel nem ismered vagy fel nem nem ismered Lint. Ez az. Ezzel a lineáris keresési algoritmust követed

Bináris keresés

A bináris keresés azért kapta a nevét, mert a bináris szó jelentése “két dologból álló vagy két dologra vonatkozó”, és az algoritmus úgy működik, hogy a bemenetet két részre osztja, amíg meg nem találja a keresett elemet. Az egyik fele tartalmazza a keresett elemet, a másik fele pedig nem. A folyamat addig folytatódik, amíg a bemenet felosztásának helye nem lesz a keresett elem. A bináris keresés alapvetően csak egy nagyon fegyelmezett megközelítése az eliminációs folyamatnak. Gyorsabb, mint a lineáris keresés, de csak rendezett sorozatokkal működik.

Egy példa ezt érthetőbbé teszi. Tegyük fel, hogy Bin nevű barátodat próbálod megtalálni (aki 175 centi magas) egy olyan egysoros sorban, ahol az emberek magassága szerint balról jobbra, a legrövidebbtől a legmagasabbig vannak sorba rendezve. Ez egy nagyon hosszú sor, és nincs időd arra, hogy egyesével végigmenj az egész soron, összehasonlítva mindenki magasságát Bin magasságával. Mit tehetsz?

Bemenj a bináris keresésbe. Kiválasztod a sor legközepén lévő személyt, és megméred a magasságát. Az illető 170 centi magas. Tehát rögtön tudod, hogy ez a személy, a tőle jobbra lévő összes emberrel együtt, nem Bin. Most, hogy a problémát kettévágtad, a sor többi részére fordítod a figyelmed, és ismét a középső személyt választod ki. Ők 175 centi magasak. Tehát kizárhatod ezt a személyt és mindenkit tőle balra, így a problémát ismét kettévágod. És így tovább. Már öt-hat ilyen felosztás után gyorsan megtalálod Bin-t, az idő töredéke alatt, ami Lin megtalálásához kellett. Ezzel a bináris keresési algoritmust követted.

Válogatás

A tételek listáinak rendezése, más néven rendezése az egyik leggyakoribb programozási feladat, amelyet fejlesztőként fogsz végezni. Itt megnézzük a két leghasznosabb rendezési algoritmust: MergeSort és QuickSort.

MergeSort

Tegyük fel, hogy a fenti példában szereplő emberek rendezett sora helyett egy rendezetlen csoportból kell létrehoznunk egy rendezett sort. Nincs sok időd, ezért kitalálsz egy stratégiát a dolgok felgyorsítására.

Először is az összezsúfolódott embercsoportot kettéosztod. Aztán a két csoport mindegyikét ismét kettéosztod, és így tovább, míg végül kizárólag egyénekkel foglalkozol. Ezután elkezded az egyéneket párosítani, és minden párban a kettő közül a magasabb álljon a másiktól jobbra. Elég hamar mindenki ezekbe a balról jobbra rendezett párokba rendeződik.

A következő lépésben a rendezett párokat négyes rendezett csoportokba kezded összevonni; majd a négyes rendezett csoportokat nyolcas rendezett csoportokba; és így tovább. Végül azt találod, hogy egy teljes, magasságban rendezett embersorod van, pont olyan, mint amilyennel fent találkoztál. Anélkül, hogy tudnád, a MergeSort algoritmust követted a bravúr teljesítéséhez.

QuickSort

A QuickSort egy kicsit túl bonyolult ahhoz, hogy könnyen elképzelhető legyen az emberekkel, ezért nézzük meg egy kicsit közelebbről a kódot. Kezdetnek képzeljük el, hogy van egy rendezetlen listád, vagy tömböd, nyolc számmal, amit rendezni szeretnél.

4 2 13 6 15 12 7 9

Használhatnád a MergeSortot, de azt hallottad, hogy a QuickSort általában gyorsabb, ezért úgy döntesz, hogy kipróbálod. Első lépésként kiválasztasz egy számot a listából, amelyet pivotnak nevezel. A megfelelő pivot szám kiválasztása nagyban befolyásolja, hogy a QuickSort milyen gyorsan működik, és vannak kész formulák, amelyeket követhetsz a jó pivotok kiválasztásához. De egyelőre maradjunk egyszerűek, és válasszuk a tömb utolsó számát a pivot számunknak: 9.

4 2 13 6 15 12 7 9

A következő lépés könnyebb követhetősége érdekében létrehozunk egy elválasztójelet a tömb elején, és azt font-jelekkel jelöljük.

# 4 2 13 6 15 12 7 9

Balról jobbra haladva a tömbünkön, a célunk az, hogy az elválasztótól balra minden, a sarkpontnál (9) kisebb számot, az elválasztótól jobbra pedig minden, a sarkpontnál nagyobb (vagy azzal egyenlő) számot helyezzünk el. A tömbünk első számával kezdjük: 4. Ahhoz, hogy ezt az elválasztótól balra helyezzük, egyszerűen csak egy elemmel feljebb toljuk az elválasztót:

4 # 2 13 6 15 12 7 9

A következő számmal ugyanígy járunk el: 2.

4 2 # 13 6 15 12 7 9

De aztán elérünk a 13-hoz, ami nagyobb, mint a 9-es pivot szám, és már az elválasztótól jobbra van. Így aztán békén hagyjuk. Ezután jön a 6, amelynek az elválasztótól balra kell kerülnie. Tehát először is kicseréljük a 13-assal, hogy a helyére kerüljön:

4 2 # 6 13 15 12 7 9

Aztán áthelyezzük az elválasztót:

4 2 6 # 13 15 12 7 9

A következő a 15, ami már az elválasztótól jobbra van, tehát békén hagyjuk. Ezután következik a 12. Ugyanez a helyzet. De a 7-nek, az utolsó számunknak, mielőtt elérjük a sarkalatos pontot, ugyanolyan segítségre van szüksége a mozgáshoz, mint a 6-nak. Ezért a 7-est felcseréljük a 13-assal, hogy a helyére kerüljön:

4 2 6 # 7 15 12 13 9

Aztán ismét áthelyezzük az elválasztót:

4 2 6 7 # 15 12 13 9

Végül elérkeztünk a pivot számunkhoz: a 9-eshez. Ugyanazt a logikát követve, mint fentebb, kicseréljük a 15-öt a 9-cel, hogy a pivot szám oda kerüljön, ahol lennie kell:

4 2 6 7 # 9 12 13 15

Mivel a 9-től balra lévő összes szám kisebb lett, mint 9, és a 9-től jobbra lévő összes szám nagyobb, mint 9, végeztünk a QuickSort első ciklusával. Ezután az elválasztó két oldalán lévő négy számból álló minden egyes számot új tömbként kezelünk, amelyre a QuickSortot alkalmazzuk. A részletektől megkíméljük önöket, de a következő körben négy számpárt kapunk, amelyekre könnyen alkalmazhatjuk a QuickSort utolsó körét. A végeredmény a következő rendezett lista lesz, amelynek létrehozása kevesebb időt vett igénybe, mint az egyszerűbb MergeSort alkalmazásával:

2 4 6 7 9 12 13 15

Sorolási algoritmusok puskatáblája

A következők a leggyakoribb rendezési algoritmusok, néhány ajánlással arra vonatkozóan, hogy mikor érdemes használni őket. Internalizáld ezeket! Mindenhol használják őket!

Heap sort: Amikor nincs szükséged stabil rendezésre, és jobban érdekel a legrosszabb eset teljesítménye, mint az átlagos eset teljesítménye. Garantáltan O(N log N), és O(1) segédterületet használ, ami azt jelenti, hogy nem fog váratlanul elfogyni a heap- vagy stackterület nagyon nagy bemeneteknél.

Introsort: Ez egy gyors rendezés, amely egy bizonyos rekurziós mélység után halomrendezésre vált, hogy megkerülje a gyors rendezés O(N²) legrosszabb esetét. Ez szinte mindig jobb, mint a sima régi gyors rendezés, mivel a gyors rendezés átlagos esetét kapjuk, garantált O(N log N) teljesítmény mellett. Valószínűleg az egyetlen ok, amiért ehelyett heap sortot kell használni, az a súlyosan memóriakorlátozott rendszerek, ahol az O(log N) veremterület gyakorlatilag jelentős.

Behelyezési sort: Amikor N garantáltan kicsi, beleértve a gyors rendezés vagy az egyesítéses rendezés alapesetét is. Ez ugyan O(N²), de nagyon kis konstans és stabil rendezés.

Bubble sort, selection sort: Amikor valami gyors és piszkos munkát végzel, és valamilyen oknál fogva nem használhatod egyszerűen a szabványos könyvtár rendezési algoritmusát. Ezek egyetlen előnye a beillesztési rendezéssel szemben, hogy valamivel könnyebben megvalósíthatóak.

Gyors rendezés: Amikor nincs szükséged stabil rendezésre, és az átlagos eset teljesítménye többet számít, mint a legrosszabb eset teljesítménye. A gyors rendezés átlagosan O(N log N), legrosszabb esetben O(N²). Egy jó implementáció O(log N) segédtárolót használ a rekurzióhoz a veremterület formájában.

Merge sort: Ha stabil, O(N log N) rendezésre van szükségünk, akkor ez az egyetlen lehetőségünk. Az egyetlen hátránya, hogy O(N) segédterületet használ, és valamivel nagyobb konstanssal rendelkezik, mint a gyors rendezés. Létezik néhány helyközi egyesítéses rendezés, de AFAIK ezek mindegyike vagy nem stabil, vagy rosszabb, mint O(N log N). Még az O(N log N) in place sortoknak is sokkal nagyobb a konstansuk, mint a sima öreg merge sortnak, így inkább elméleti érdekességek, mint hasznos algoritmusok.