aloittelevat Lajittelualgoritmit JavaScript: Bubble, Selection & Insertion Sort

se, että tietokokonaisuutesi on järjestetty, tuo vain lisää aikaa ja resursseja hallinnointiin ja hakuun. Se, onko tietosi lajiteltu vai ei, vaikuttaa suoraan siihen, mitä hakumenetelmiä voit käyttää, ja se voi tarkoittaa eroa miljoonan toiminnon tai 10 tehtävän haun välillä, kuten Binäärihaussa.

yksinkertaisuuden vuoksi keskitymme vain numeroiden lajitteluun pienimmästä suurimpaan, mutta nämä algoritmit ovat helposti muunneltavissa muihin lajittelutavoitteisiin. Muista, että nämä ovat yleisempiä käsitteitä ja malleja ja vähemmän ”miten-to” tietojen lajitteluun, koska erityinen toteutus voi vaihdella paljon, mutta lopulta se voi käsitteellisesti muistuttaa näitä malleja.

tässä on 50 satunnaisluvun harjoitusjoukko.

const unsortedArr = ;

edellytykset

aion katsoa kaikkea Ison O-notaation linssin läpi, joten ymmärtämisestä, miten monimutkaisuus kasvaa ajan myötä, on paljon apua.

Bubble Sort

tämä on lajittelumenetelmien ”Hello World”, Ei mitään hullua, mutta homma hoituu.

jokaisesta rivin alkiosta haluamme tarkistaa, onko seuraava kohde suurempi, jos se sitten vaihtaa niiden indeksit matriisissa. Jotta lajiteltuja numeroita ei laskettaisi uudelleen, aloitetaan rivin takaa, kun taas toinen for loop saa edeltävän numeron. Näin kaikki suurimmat arvot rakentuvat eli ”kuplivat” päähän.

 Bubble Sort Animation

Graphic/Animation thanks to VisuAlgo.net

meidän versiomme toimii animaatiosta käänteisesti, mutta se on tarpeeksi lähellä.

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

valinta Lajittelu

valinta lajittelu toimii kuin vastakohta kupla lajittelu, kun taas kupla lajittelu työntää kaikki suurimmat arvot loppuun nyt aiomme työntää vähimmäisarvot alkuun.

joka kerta kun se kiertää joukon yli, se valitsee pienimmän arvon, jos se löytää pienemmän arvon, josta sitten tulee uusi alin arvo. Kun silmukka on valmis se ottaa että minimi ja laittaa sen edessä array ennen silmukan uudelleen. Näin jokaisen iteraation pienin arvo pinotaan eteen, kunnes koko joukko on lajiteltu.

Valintalajittelu animaatio

graafinen/animaatio Kiitos Visualgon.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

henkilökohtainen suosikkini ja kolmikosta suoriutunein, insertion sort, muistuttaa enemmän sitä, miten lajittelisit jotain käsin.

katsomme array kahtena osana, lajiteltu ja lajittelematon, joka kerta kun löydämme uusi arvo me silmukka takaisin löytää sen paikka lajiteltu puoli. Jokainen lisäys meidän lajiteltu ryhmä kasvaa, kunnes se on koko joukko.

Insertion Sort Animation

graafinen/animaatio Kiitos Visualgon.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));

Vertailu

yksi ongelma ison O-notaation käytössä algoritmien vertailussa on se, että se perustuu huonompaan skenaarioon, joka voi olla sama eri algoritmeissa antaen väärän illuusion siitä, että ne ovat samanarvoisia. Vaikka kupla -, valinta-ja Lisäyslajit ovat kaikki O(n^2), se ei kerro meille paljoakaan keskiarvosta tai parhaassa tapauksessa tai siitä, miten ne vaihtelevat tietorakenteen mukaan.

Insertion sort voittaa joka kerta. Se on myös etu ei tarvitse olla koko array ennen aloittamista, jonka avulla voit lajitella asioita reaaliajassa, kun tiedot tulevat.

pidä tämä mielessä, koska sinun ei pitäisi päättää, mikä algoritmi on ”paras” ennen kuin harkitset, miten tietosi on jo järjestetty.

johtopäätös

nämä kolme eivät ole läheskään parhaita ratkaisuja suurten tietomäärien tehokkaaseen lajitteluun, mutta ne ovat joitain intuitiivisimpia kastamaan varpaasi siihen, mikä voi olla ylivoimainen valtameri. 🌊