Begyndersorteringsalgoritmer i JavaScript: Bubble, Selection & Insertion Sort

at have dine datasæt arrangeret alt vil kun tilføje mere tid og ressourcer til at styre og søge igennem. Uanset om dine data er sorteret eller ej, vil det direkte påvirke, hvilke søgemetoder du kan bruge og kan betyde forskellen mellem en søgning, der tager en million operationer eller tager 10, som med binær søgning.

for enkelhedens skyld vil vi kun fokusere på at sortere en række tal fra mindst til største, men disse algoritmer kan let ændres til andre sorteringsmål. Husk, at dette er mere generelle begreber og mønstre og mindre af en “vejledning” til sortering af data, da din særlige implementering kan variere meget, men i sidste ende kan den konceptuelt ligne disse mønstre.

her er den praksis vifte af 50 tilfældige tal.

const unsortedArr = ;

forudsætninger

jeg vil se på alt gennem linsen til Big O Notation, så det vil være meget nyttigt at forstå, hvordan kompleksiteten vokser over tid.

Bubble Sort

dette er “Hej Verden” af sorteringsmetoder, intet vanvittigt, men det får jobbet gjort.

for hvert element i arrayet vil vi kontrollere, om det næste element er større, hvis det derefter byttes deres indekser i arrayet. For at undgå at sammenligne sorterede tal starter vi fra bagsiden af arrayet, mens en anden for loop får det foregående nummer. På denne måde opbygges alle de største værdier eller “bobler op” i slutningen.

Boblesorteringsanimation

grafik / Animation takket være VisuAlgo.net

vores version fungerer omvendt fra animationen, men den er tæt nok.

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));

valg sortering

valg sortering fungerer som det modsatte af boblesortering, mens boblesortering skubber alle de største værdier til slutningen nu skal vi skubbe minimumsværdierne til starten.

hver gang den løber over arrayet, vælger den den mindste værdi, hvis den finder en lavere værdi, så bliver den den nye laveste værdi. Når sløjfen er færdig, vil det tage det minimum og sætte det på forsiden af arrayet, før du starter sløjfen igen. På denne måde stables den laveste værdi af hver iteration på fronten, indtil hele arrayet er sorteret.

valg Sorter Animation

grafik/Animation takket være 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));

Indsætningssortering

min personlige favorit og den mest performant af de tre, indsætningssortering, ligner mere, hvordan du ville sortere noget i hånden.

vi ser på arrayet som to dele, den sorterede og usorterede, med hver gang vi finder en ny værdi, løber vi tilbage for at finde sin plads i den sorterede halvdel. Med hver tilføjelse vokser vores sorterede gruppe, indtil den er hele arrayet.

Indsætningssorteringsanimation

grafik/Animation takket være 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));

sammenligning

et problem med at bruge Big O Notation til sammenligning af algoritmer er, at det er baseret på det værre tilfælde, hvilket kan være det samme på tværs af algoritmer, der giver den falske illusion, at de er ens. Mens boble -, valg-og Indsættelsessorter alle er O(n^2), fortæller det os ikke meget om gennemsnittet eller det bedste tilfælde, eller hvordan de varierer med datastrukturen.

indsættelse sort vinder hver gang. Det har også fordelen ved ikke at skulle have hele arrayet, før du starter, hvilket giver dig mulighed for at sortere ting i realtid, når data kommer ind.

husk dette, fordi du ikke skal beslutte, hvilken algoritme der er “bedst”, før du overvejer, hvordan dine data allerede er organiseret.

konklusion

disse tre er langt fra de bedste løsninger til effektiv sortering af store mængder data, men de er nogle af de mest intuitive at dyppe tæerne i, hvad der kan være et overvældende hav. 🌊