Begynnersorteringsalgoritmer I JavaScript: Boble, Utvalg Og Innsettingssortering

Å ha datasettene dine ordnet, vil bare legge til mer tid og ressurser for å administrere og søke gjennom. Om dataene dine er sortert eller ikke, vil direkte påvirke hvilke søkemetoder du kan bruke, og kan bety forskjellen mellom et søk som tar en million operasjoner eller tar 10, som Med Binært Søk.

for enkelhets skyld skal vi bare fokusere på å sortere en rekke tall fra minst til størst, men disse algoritmene er lett modifiserbare for andre sorteringsmål. Husk at disse er mer generelle begreper og mønstre og mindre av en «how-to» for sortering av data siden din spesielle implementering kan variere mye, men til slutt kan det konseptuelt ligne disse mønstrene.

Her er praksis rekke 50 tilfeldige tall.

const unsortedArr = ;

Forutsetninger

jeg skal se på alt gjennom linsen Av Big O Notasjon, så forstå hvordan kompleksiteten vokser over tid vil være svært nyttig.

Bubble Sort

Dette er «Hei Verden» av sorteringsmetoder, ingenting gal, men det får jobben gjort.

for hvert element i matrisen vil vi sjekke om neste element er større, hvis det da byttes indeksene i matrisen. For å unngå å rekomparere sorterte tall starter vi fra baksiden av arrayet mens en annen for loop får det forrige nummeret. På denne måten bygger alle de største verdiene opp, eller «bobler opp», på slutten.

 Boble Sorter Animasjon

Grafikk/Animasjon takket være VisuAlgo.net

vår versjon fungerer omvendt fra animasjonen, men den er nær 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));

Utvalgssortering

utvalgssortering fungerer som det motsatte Av Boblesortering, mens boblesortering skyver alle de største verdiene til slutten nå skal vi skyve minimumsverdiene til start.

hver gang den går over matrisen, velger den den minste verdien, hvis den finner en lavere verdi som da blir den nye laveste verdien. Når sløyfen er ferdig, tar det minimum og legger det på forsiden av arrayet før du starter sløyfen igjen. På denne måten stables den laveste verdien av hver iterasjon på forsiden til hele arrayet er sortert.

 Utvalg Sorter Animasjon

Grafikk/Animasjon takket Være VisuAlgo.netto

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

Innsettingssortering

min personlige favoritt og den mest effektive av de tre, innsettingssortering, ligner mer på hvordan du vil sortere noe for hånd.

vi ser på matrisen som to deler, den sorterte og usorterte, med hver gang vi finner en ny verdi, går vi tilbake for å finne sin plass i den sorterte halvdelen. Med hvert tillegg vokser vår sorterte gruppe til det er hele arrayet.

 Innsetting Sorter Animasjon

Grafikk/Animasjon takket Være VisuAlgo.netto

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 Å bruke Big O-Notasjon for å sammenligne algoritmer er at den er basert på verre tilfelle, som kan være det samme på tvers av algoritmer som gir den falske illusjonen om at de er like. Mens Boble, Utvalg og Innsettingssorter er Alle O (n^2), forteller det oss ikke mye om gjennomsnittlig eller best case scenario eller hvordan de varierer med datastrukturen.

Innsettingssortering vinner hver gang. Det har også fordelen av å ikke måtte ha hele arrayet før du starter, noe som gjør at du kan sortere ting i sanntid når data kommer inn.

Husk dette fordi du ikke bør bestemme hvilken algoritme som er «best» før du vurderer hvordan dataene dine allerede er organisert.

Konklusjon

disse tre er langt fra de beste løsningene for å effektivt sortere store mengder data, men de er noen av de mest intuitive å dyppe tærne inn i det som kan være et overveldende hav. 🌊