kezdő rendezési algoritmusok a JavaScript-ben: Bubble, Selection & Insertion Sort

ha az adatkészleteket minden akarva-akaratlanul elrendezi, akkor csak több időt és erőforrást fog hozzáadni a kezeléshez és a kereséshez. Az, hogy az adatok rendezve vannak-e vagy sem, közvetlenül befolyásolja, hogy milyen keresési módszereket használhat, és jelentheti a különbséget egy millió műveletet végző keresés vagy 10, mint a bináris keresésnél.

az egyszerűség kedvéért csak a számok tömbjének rendezésére fogunk összpontosítani a legkisebbtől a legnagyobbig, de ezek az algoritmusok könnyen módosíthatók más rendezési célokra. Ne feledje, hogy ezek általánosabb fogalmak és minták, és kevésbé “hogyan kell” az adatok rendezéséhez, mivel az adott megvalósítás sokat különbözhet, de végül koncepcionálisan hasonlíthat ezekre a mintákra.

itt a gyakorlat tömb 50 véletlen számok.

const unsortedArr = ;

előfeltételek

mindent a Big O jelölés lencséjén keresztül fogok nézni, így nagyon hasznos lesz megérteni, hogy a komplexitás hogyan növekszik az idő múlásával.

Bubble Sort

ez a “Hello World” rendezési módszerek, semmi őrült, de ez lesz a munka.

a tömb minden egyes eleméhez ellenőrizni akarjuk, hogy a következő elem nagyobb-e, ha ezután cseréljük az indexüket a tömbben. A rendezett számok újraértékelésének elkerülése érdekében a tömb hátuljáról indulunk, míg egy másik for loop megkapja az előző számot. Így az összes legnagyobb érték felépül, vagy” buborékok fel”, a végén.

 buborék rendezés animáció

grafikus / animáció köszönhetően VisuAlgo.net

verziónk az animációtól fordítva működik, de elég közel van.

const bubble = arr => { const swap = (list, a, b) => , list] = , list]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr > arr) swap(arr, j, j + 1); }; }; return arr;};console.log(bubble(unsortedArr));

kiválasztás Rendezés

kiválasztás rendezés működik, mint az ellenkezője a buborék rendezés, míg buborék rendezés nyomja az összes legnagyobb értékek a végén most megyünk, hogy álljon a minimális értékeket a kezdet.

minden alkalommal, amikor a tömb fölé hurkol, kiválasztja a legkisebb értéket, ha alacsonyabb értéket talál, akkor ez lesz az új legalacsonyabb érték. Amikor a hurok kész lesz, hogy a minimális és tedd az első a tömb megkezdése előtt a hurok újra. Így az egyes iterációk legalacsonyabb értéke az elejére kerül, amíg az egész tömb rendezésre nem kerül.

Válogatás Rendezés animáció

grafikus/animáció köszönhetően VisuAlgo.net

const selection = arr => { const swap = (list, a, b) => , list] = , list]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr < arr) min = j; }; swap(arr, i, min); }); return arr;};console.log(selection(unsortedArr));

Beszúrási Rendezés

személyes kedvencem és a három közül a legjobban teljesítő, beillesztési rendezés, jobban hasonlít ahhoz, ahogyan kézzel rendezne valamit.

a tömböt két részre, a rendezett és a rendezetlen részre tekintjük, és minden alkalommal, amikor új értéket találunk, visszafordulunk, hogy megtaláljuk a helyét a rendezett félben. Minden egyes kiegészítéssel a rendezett csoportunk addig növekszik, amíg az egész tömb nem lesz.

Beszúrási Rendezés animáció

grafikus/animáció köszönhetően VisuAlgo.net

const insertion = arr => { arr.forEach((item, i) => { let num = arr; let j; for (j = i - 1; j >= 0 && arr > num; j--) { arr = arr; }; arr = num; }); return arr;};console.log(insertion(unsortedArr));

összehasonlítás

a Big O jelölés algoritmusok összehasonlításának egyik problémája az, hogy a rosszabb eseten alapul, amely ugyanaz lehet az algoritmusok között, ami azt a hamis illúziót kelti, hogy egyenlőek. Míg a buborék, a kiválasztás és a Beillesztés rendje mind O(n^2), ez nem sokat mond nekünk az átlagos vagy a legjobb esetről, vagy arról, hogy ezek hogyan változnak az adatstruktúrától függően.

a beszúrási rendezés minden alkalommal nyer. Ennek az az előnye is, hogy indítás előtt nincs szükség a teljes tömbre, amely lehetővé teszi a dolgok valós idejű rendezését az adatok beérkezésekor.

ne feledje ezt, mert nem szabad eldöntenie, hogy melyik algoritmus a “legjobb”, mielőtt megvizsgálná az adatok már rendezését.

következtetés

ez a három messze nem a legjobb megoldás a nagy mennyiségű adat hatékony rendezésére, de ezek a leg intuitívabbak arra, hogy belemerítsék a lábujjaikat egy elsöprő óceánba. 🌊