algoritmi de sortare începător în JavaScript: Bubble, selecție și sortare inserție

având seturile de date aranjate toate vrând-nevrând va adăuga doar mai mult timp și resurse pentru a gestiona și de căutare prin. Dacă datele sunt sortate sau nu va afecta în mod direct ce metode de căutare puteți utiliza și poate însemna diferența dintre o căutare a lua un milion de operațiuni sau de a lua 10, cum ar fi cu Căutare binară.

de dragul simplității, ne vom concentra doar pe sortarea unei serii de numere de la cel mai mic la cel mai mare, dar acești algoritmi sunt ușor modificabili pentru alte obiective de sortare. Rețineți că acestea sunt concepte și modele mai generale și mai puțin un „cum să” pentru sortarea datelor, deoarece implementarea dvs. particulară poate diferi foarte mult, dar în cele din urmă se poate asemăna conceptual cu aceste modele.

Iată matricea practică de 50 de numere aleatoare.

const unsortedArr = ;

premise

voi privi totul prin lentila notației Big O, astfel încât înțelegerea modului în care complexitatea crește în timp va fi foarte utilă.

Bubble Sort

aceasta este „Hello World” de metode de sortare, nimic nebun, dar devine treaba.

pentru fiecare element din matrice dorim să verificăm dacă următorul element este mai mare, dacă este apoi swap indexurile lor în matrice. Pentru a evita recompararea numerelor sortate, vom începe din spatele matricei în timp ce un alt for loop primește numărul precedent. În acest fel, toate cele mai mari valori se acumulează, sau „bule”, la sfârșit.

 Bubble Sortare animație

grafic/animație datorită VisuAlgo.net

versiunea noastră funcționează în sens invers față de animație, dar este destul de aproape.

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

Sortare selecție

sortare selecție funcționează ca opusul sortare bule, în timp ce sortare bule este împingând toate cele mai mari valori până la sfârșit acum vom împinge valorile minime la început.

de fiecare dată când se învârte peste matrice, selectează cea mai mică valoare, dacă găsește o valoare mai mică care atunci devine noua valoare cea mai mică. Când bucla se face, va lua acel minim și o va pune pe partea din față a matricei înainte de a începe din nou bucla. În acest fel, cea mai mică valoare a fiecărei iterații este stivuită pe față până când întreaga matrice este sortată.

selecție Sortare animație

grafic/animație datorită 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));

Insertion Sort

preferatul meu personal și cel mai performant dintre cele trei, insertion sort, este mai asemănător cu modul în care ați sorta ceva manual.

ne uităm la matrice ca două părți, sortate și nesortate, cu fiecare dată când găsim o nouă valoare ne bucla înapoi pentru a găsi locul său în jumătatea sortate. Cu fiecare adăugare, grupul nostru sortat crește până când este întreaga gamă.

Inserare Sortare animație

grafic/animație datorită 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));

comparație

o problemă cu utilizarea notației Big O pentru compararea algoritmilor este că se bazează pe scenariul cel mai rău caz, care poate fi același între algoritmi, dând falsa iluzie că sunt egali. În timp ce tipurile de bule, selecție și Inserare sunt toate O(N^2), Acest lucru nu ne spune prea multe despre scenariul mediu sau cel mai bun caz sau despre modul în care acestea variază în funcție de structura datelor.

sortarea inserției câștigă de fiecare dată. De asemenea, are avantajul de a nu fi nevoie să aveți întreaga matrice înainte de a începe, ceea ce vă permite să sortați lucrurile în timp real pe măsură ce datele intră.

rețineți acest lucru, deoarece nu ar trebui să decideți ce algoritm este „cel mai bun” înainte de a lua în considerare modul în care datele dvs. sunt deja organizate.

concluzie

aceste trei sunt departe de a fi cele mai bune soluții pentru sortarea eficientă a unor cantități mari de date, dar sunt unele dintre cele mai intuitive pentru a vă scufunda degetele de la picioare în ceea ce poate fi un ocean copleșitor. 🌊