Sissejuhatus algoritmide sortimisse JavaScriptis

Sarnaselt enamiku muude programmeerimiskeeltega võite sattuda stsenaariumitesse, kus peate JavaScriptis mõned numbrid järjestama kasvavas või kahanevas järjekorras. Selle valmistamiseks võime kasutada paljusid algoritme, nagu mullide sortimine, sortimis sortimine, liitmine, Quicksort jne. Need algoritmid erinevad mitte ainult tööpõhimõttest, vaid ka nende erinevatel nõudmistel mälu ja ajakulu osas, lähme uurige mõnda olulist sortimisalgoritmi põhjalikumalt ja vaadake, kuidas saate neid oma JavaScripti koodis kasutada.

Kuus parimat sortimisalgoritmi JavaScriptis

Siin on mõned JavaScripti sortimisalgoritmid, mida on allpool selgitatud näidetega:

1. Mullide sortimise algoritm

Mullide sortimist, mida peetakse selle kaubanduse üheks kõige tavalisemaks tööriistaks, luuakse silmus, mis võrdleb massiivi iga üksust teise üksusega. Kui võrreldav toode on väiksem kui käsikäes, vahetame nende kohad välja. See jätkub, kuni meil on pass, kus ükski massiivi element pole suurem kui tema kõrval asuv üksus.

Mullide sortimisel on O (n 2 ) aja keerukus ja O (n) ruumi keerukus.

Kood:

function swap(arr, firstIndex, secondIndex)(
var temp = arr(firstIndex);
arr(firstIndex) = arr(secondIndex);
arr(secondIndex) = temp;
)
function bubbleSortAlgo(arraaytest)(
var len = arraaytest.length,
i, j, stop;
for (i=0; i < len; i++)(
for (j=0, stop=len-i; j < stop; j++)(
if (arraaytest(j) > arraaytest(j+1))(
swap(arraaytest, j, j+1);
)
)
)return arraaytest;
)
console.log(bubbleSortAlgo((3, 6, 2, 5, -75, 4, 1)));

Väljund:

2. Valiku sortimise algoritm

Nüüd, kui oleme mullide sortimise algoritmi arutamise lõpetanud, heidame pilgu lihtsalt populaarsele sorteerimisalgoritmile nimega Sort sortimine.

Erinevalt Bubble Sortist keskendume sortimises massiivi väikseima väärtuse leidmisele. Siin on samm-sammuline jaotus valiku sortimise toimimise kohta:

  • Eeldame, et massiivi esimene element on väikseim.
  • Võrdleme seda kaupa massiivi järgmise elemendiga.
  • Kui järgmine üksus on käepärast väiksem, määrasime järgmise üksuse väikseimaks uueks väärtuseks.
  • Kordame neid samme, kuni jõuame massiivi lõpuni.
  • Kui leiame massiivist väiksema väärtuse kui see, millega alustasime, vahetame nende positsioonid.
  • Teeme pidevalt võrdlusi ja liigume järgmise juurde. Kuni kogu massiiv on sorteeritud.

Nii nagu mullide sortimise algoritm, on ka valiku sorteerimine O (n 2 ) aja keerukus ja O (n) ruumi keerukus.

Kood:

function SelectionSortAlgo(array, compare_Function) (
function comp(a, b) (
return a - b;
)
var min = 0;
var index = 0;
var temp = 0;
compare_Function = compare_Function || compare;
for (var i = 0; i < array.length; i += 1) (
index = i;
min = array(i);
for (var j = i + 1; j < array.length; j += 1) (
if (compare_Function(min, array(j)) > 0) (
min = array(j);
index = j;
)
)
temp = array(i);
array(i) = min;
array(index) = temp;
)
return array;
)
console.log(SelectionSortAlgo((9, 15, 2, 44, -1, 36, 1), function(a, b) ( return a - b; )));

Väljund:

3. Ühendamise sortimisalgoritm

Sarnaselt mullide sortimise ja valiku sortimisega on ka ühendamise sortimine arvutiteaduses üks populaarsemaid sortimisalgoritme, saate seda rakendada enamikus programmeerimiskeeltes ja see on hea jõudlusega, ilma et see oleks ressursside jaoks liiga puudulik.

Ühenda sorteerimine massiivi või mis tahes elementide loendi sortimiseks kasutab jagamise ja vallutamise meetodit. Mõiste jagab ja vallutab tähendab, et jagame ühe suure probleemi mitmeks väiksemaks probleemiks ja lahendame need väikesed probleemid. Kui väiksemad probleemid on lahendatud, ühendame tulemused, mis annavad lahenduse suurele probleemile.

Algoritmi mõistmine on tegelikult lihtne:

  • Jagame antud massiivi n-ks massiiviks, millest igaüks koosneb ainult 1 elemendist.
  • Ühendage massiivid uue massiivi saamiseks.
  • Korrake 2. sammu, kuni alles on jäänud ainult 1 massiiv, mis on sorteeritud massiiv.

Kood:

function merge_sort_algo(left, right)
(
var i = 0;
var j = 0;
var result = ();
while (i < left.length || j < right.length) (
if (i === left.length) (
// j is the only index left_part
result.push(right(j));
j++;
)
else if (j === right.length || left(i) <= right(j)) (
result.push(left(i));
i++;
) else (
result.push(right(j));
j++;
)
)
return result;
)
console.log(merge_sort_algo((1, 44, 6), (84, 7, 5)));

Väljund:

4. Kiire sortimise algoritm

Quicksort on üks kõige tõhusamaid viise elementide sortimiseks arvutisüsteemides. Similor sorteerimise ühendamiseks töötab Quicksort jagamise ja vallutamise algoritmil. Selles leiame massiivist pöördeüksuse, et võrrelda kõigi teiste elementide massiive ja seejärel liigutame üksusi viisil, kus kõik üksused enne meie valitud pöördeüksusi on väiksemad ja kõik üksused pärast pöördeüksust on suurema suurusega. Kui oleme seda teinud, on peamine, et teeme seda korduvalt ja meil on oma sorteeritud massiiv.

Järgmised toimingud, mida saab Quicksort-algoritmi rakendamiseks järgida:

  • Valime massiivi elemendi ja kutsume seda “Pivot Point”
  • Alustame kursorit, mida nimetatakse vasakpoolseks osutiks, millest asub massiivi esimene element.
  • Samamoodi alustame massiivi viimasest üksusest osutit, mida nimetatakse paremaks osutiks.
  • Kui elemendi väärtust vasakpoolses kursoris on valitud pöördepunktiga võrreldes vähem, liigutame vasakpoolset kursorit vasakule (lisame sellele +1) ja jätkame korramist, kuni vasaku osuti väärtus on suurem kui pöördepunkti väärtus või sellega võrdne.
  • Kui elemendi väärtus loendis paremal asuval osutil on suurem kui pöördeelemendi väärtus, siis modereerime parema kursori vasakule. Korrake seda seni, kuni väärtus parempoolsel küljel on madalam (või sellega võrdne) pöörde väärtus.
  • Kui vasaku osuti väärtus on parema osuti väärtusest väiksem või sellega võrdne, vahetage väärtused.
  • Liigutage paremat kursorit vasakule ükshaaval, vasakut kursorit paremale ükshaaval.
  • Korrake, kuni vasak ja parem kursor kokku saavad.

Kood:

function quickSortAlgo(origArray) (
if (origArray.length <= 1) (
return origArray;
) else (
var left = ();
var right = ();
var newArray = ();
var pivot = origArray.pop();
var length = origArray.length;
for (var i = 0; i < length; i++) (
if (origArray(i) <= pivot) (
left.push(origArray(i));
) else (
right.push(origArray(i));
)
)
return newArray.concat(quickSortAlgo(left), pivot, quickSortAlgo(right));
)
)
var myArray = (13, 50, 2, 45, -1, 74, 11 );
var arreySorted = quickSortAlgo(myArray);
console.log(arreySorted);

Väljund:

5. Sisestuse sortimise algoritm

Rakendamise lihtsuse osas on sisestamise sort laialt tuntud kui üks lihtsamaid algoritme. Lisamissorteerimise korral võrreldakse massiivi elemente üksteisega ja järjestatakse seejärel kindlas järjekorras. See on väga sarnane kaartide tekki paigutamisega. Nimi sisestamise sort tuleneb elemendi valimisest, selle õigesse kohta sisestamisest ja kõigi elementide kordamiseks.

Algoritm töötab järgmiselt:

  • Massiivi esimest elementi peetakse juba sorteerituks.
  • Valige massiivi järgmine element.
  • Võrrelge valitud elementi kõigi massiivi elementidega.
  • Nihutage massiivi iga elementi, mis on suurem kui valitud elemendi väärtus.
  • Sisestage element
  • Korrake 2. kuni 5. sammu, kuni massiiv on sorteeritud.

Kood:

function insertion_Sort_algo(arr)
(
for (var i = 1; i < arr.length; i++)
(
if (arr(i) < arr(0))
(
arr.unshift(arr.splice(i, 1)(0));
)
else if (arr(i) > arr(i-1))
(
continue;
)
else (
for (var j = 1; j < i; j++) (
if (arr(i) > arr(j-1) && arr(i) < arr(j))
(
arr.splice(j, 0, arr.splice(i, 1)(0));
)
)
)
)
return arr;
)
console.log(insertion_Sort_algo((44, 20, 26, 54, -9, 41, 16)));

Väljund:

6. Hunnikute sortimise algoritm

Hunnikute sorteerimine on elementide sortimisviis, kasutades andmehinda „Heap“. Meetod on üsna sarnane valiku sorteerimistehnikaga, mida arutasime varem. Nüüd võite mõelda, mis on Hunnikud ja kuidas need on määratletud, enne kui algoritmi juurde jõuame, mõistame kõigepealt hunnikuid.

Lühidalt - hunnik on binaarne puu, millele on lisatud mõned reeglid. Üks reegel väidab, et hunnikus peab puu olema täielik binaarne puu, mis tähendab lihtsalt, et enne uue lisamist on vaja kõik sõlmed praegusel tasemel täita. Järgmine hunniku reegel on see, et hunniku elemendi väärtustega peab olema määratletud lapse ja vanema suhe.

Minihunnikus peab vanema väärtus olema väiksem kui tema lastel. Maksimaalses hunnikus, nagu võite arvata, peab vanema väärtus olema suurem kui tema lapsel.

Nüüd, kui definitsioonid on valesti, vaatame, kuidas hunnik töötab:

  • Esmalt ehitame maksimaalse hunniku, mis tagab, et kõrgeima väärtusega element on ülaosas.
  • Lülitame ülemise elemendi hunniku viimase elemendiga välja ja eemaldame ülemise elemendi hunnikust ja salvestame selle sorteeritud massiivi.
  • Kordame esimest ja teist sammu, kuni hunnikusse on jäänud ainult üks element.

Üks asi, mida tuleks meeles pidada, on see, et Java-kõnesid ei toetata hunnikuid loomulikult, seetõttu peame kasutama hunnikuid massiivide abil. Hunnikute sorteerimise ruumiline keerukus on O (1), mis on suurepärane ja kuigi mõistmise ja juurutamise osas on see liitmise või sisestamise sortimisega võrreldes pisut keerulisem, arvan, et jõudluse eeliste jaoks on seda lõppkokkuvõttes parem kasutada suured projektid.

Kood:

var arrLength;
function heapRoot(input, i) (
var left = 2 * i + 1;
var right = 2 * i + 2;
var max = i;
if (left input(max)) (
max = left;
)
if (right input(max)) (
max = right;
)
if (max != i) (
swap(input, i, max);
heapRoot(input, max);
)
)
function swap(input, index_A, index_B) (
var temp = input(index_A);
input(index_A) = input(index_B);
input(index_B) = temp;
)
function heapSortAlgo(input) (
arrLength = input.length;
for (var i = Math.floor(arrLength / 2); i >= 0; i -= 1) (
heapRoot(input, i);
)
for (i = input.length - 1; i > 0; i--) (
swap(input, 0, i);
arrLength--;
heapRoot(input, 0);
)
)
var arr = (12, 10, 22, 55, -8, 64, 14);
heapSortAlgo(arr);
console.log(arr);

Väljund:

Järeldus

Sorteerimine on JavaScriptiga rakenduste ja veebisaitide loomise oluline osa. Nüüd, kui olete tutvunud mõne kõige olulisema algoritmiga, mille abil tööd teha, peaksite tundma end JS Arenduses kindlamalt.

Üks oluline asjaolu, mida mitmesuguse sorteerimise puhul tuleks meeles pidada, on see, et te ei pea tegelikult liiga palju endale rõhutama, millist algoritmi enamikul juhtudel kasutada. Nüüd, kui arvuti riistvara on nii võimas, ei riku kaasaegsed telefoni- ega lauaarvutiprotsessorid isegi sadu elemente mõne millisekundi jooksul sorteerimisel higi. Sorteerimise algoritmide muutmine võib olla kasulik ainult juhul, kui teil on aeglane riistvara või kui olete optimeerinud iga koodiosa.

Soovitatavad artiklid

See on juhend algoritmide sortimiseks JavaScriptis. Siin käsitleme JavaScripti 6 parimat sortimisalgoritmi koos näidete ja koodi rakendamisega. Lisateabe saamiseks võite vaadata ka järgmisi artikleid -

  1. JavaScripti koostajad
  2. JavaScriptis tagurpidi
  3. Sissejuhatus JavaScripti
  4. Ruudud Java-s
  5. Kiire sortimise algoritmid Java-s
  6. Massiivid andmestruktuuris
  7. C ++ algoritm | C ++ algoritmi näited

Kategooria:

Tarkvaraarendus