Bevezetés a rendezési algoritmusokba a JavaScript-ben

A legtöbb más programozási nyelvhez hasonlóan olyan forgatókönyvekbe is belefuthat, amelyekben néhány számot JavaScript szerint növekvő vagy csökkenő sorrendbe kell rendezni. Ennek elkészítéséhez számos algoritmust használhatunk, mint például a Bubble sort, Selection Sort, Merge sort, Quicksort stb. Ezek az algoritmusok nem csak működésükben különböznek egymástól, hanem mindegyiküknek különféle igényei vannak a memória és a felhasznált idő szempontjából. mélyebben foglalkozzon néhány fontos rendezési algoritmussal, és nézd meg, hogyan lehet ezeket használni a JavaScript-kódban.

A 6 legnépszerűbb rendezési algoritmus a JavaScript-ben

Az alábbiakban néhány példát találtunk a javascript szerinti rendezési algoritmusokra:

1. Bubble Sort Algorithm

A kereskedelem egyik leggyakoribb eszközének tekintve a Bubble sort egy hurok létrehozásával működik, amely összehasonlítja a tömb minden elemét egy másik elemmel. Ha az összehasonlított elem kisebb, mint a kezünkben, akkor cseréljük a helyüket. Ez addig folytatódik, amíg meg nem kapunk egy átadást, ahol a tömb egyetlen elem sem nagyobb, mint a mellette lévő elem.

A Bubble Sort O (n 2 ) idő bonyolultsága és O (n) tér bonyolultsága van.

Kód:

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

Kimenet:

2. Kiválasztási rendezési algoritmus

Most, hogy befejeztük a Bubble Sort Algorithm megvitatását, vessünk egy pillantást éppen olyan népszerű algoritmusra, amelyet a Selection Sort néven sorolunk.

A Bubble Sort-től eltérően arra koncentrálunk, hogy a tömb legkisebb értékét keressük meg, hogy a rendezés megtörténjen. Itt van egy lépésről lépésre a Selection Sort működése:

  • Feltételezzük, hogy a tömb első eleme a legkisebb.
  • Összevetjük ezt a tételt a tömb következő tételével.
  • Ha a következő elem kisebb, mint a jelenlegi, akkor a következő elemet állítjuk be az új legkisebb értékként.
  • Addig ismételjük ezeket a lépéseket, amíg el nem éri a tömb végét.
  • Amikor azt találjuk, hogy a tömbben kisebb érték van, mint amivel kezdtünk, akkor kicseréljük a pozícióikat.
  • Folytatjuk az összehasonlításokat, és továbbmegyünk a következő elemhez. Amíg a teljes tömb nincs rendezve.

Csakúgy, mint a Bubble Sort algoritmus, a Selection sort O (n 2 ) idő bonyolultsága és O (n) tér bonyolultsága jellemzi.

Kód:

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

Kimenet:

3. Összevonási rendezési algoritmus

A Bubble Sort és a Selection Sorthez hasonlóan a Merge sort a számítógépes tudomány egyik népszerű válogatási algoritmusa, a legtöbb programozási nyelven megvalósítható, és jó teljesítményű, anélkül, hogy erőforrásokra lenne szükség.

Az Egyesítés rendezése a Osztás és Hódítás módszert használja a tömb vagy az elemek listájának rendezéséhez. A felosztás és meghódítás kifejezés azt jelenti, hogy egy nagy problémát több kisebb problémára osztunk, majd ezeket a kis problémákat megoldjuk. A kisebb problémák megoldása után egyesítjük az eredményeket, amelyek megoldást jelentenek a nagy problémára.

Az algoritmus megértése valójában egyszerű:

  • A megadott tömböt n tömbre osztjuk, és mindegyik tömb mindössze 1 elemet tartalmaz.
  • Egyesítse a tömböket egy új tömb előállításához.
  • Ismételje meg a 2. lépést, amíg csak 1 tömb marad hátra, ez lesz a rendezett tömb.

Kód:

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

Kimenet:

4. Gyors rendezési algoritmus

A Quicksort az egyik leghatékonyabb módszer az elemek rendezéséhez a számítógépes rendszerekben. A szétválasztás similorjának összeolvasztása érdekében a Quicksort a split and conquer algoritmussal működik. Ebben találunk egy pivot elemet a tömbben, hogy összehasonlítsuk az összes többi elem tömböt, majd mozgatjuk az elemeket oly módon, hogy a kiválasztott pivot elemek előtti összes elem kisebb legyen, és az összes pivot elem nagyobb legyen. Miután ezt megtettük, a legfontosabb az, hogy folyamatosan ezt ismételjük meg, és megvan a rendezett tömbünk.

A következő lépések követhetők a quicksort algoritmus megvalósításához:

  • Kiválasztjuk a tömb egy elemét, és “Pivot Point” -nak hívjuk.
  • Elindítunk egy bal oldali mutatónak nevezett mutatót, amely a tömb első eleménél található.
  • Hasonlóképpen elindítunk egy jobb mutatónak nevezett mutatót a tömb utolsó eleménél.
  • Ha az elem értéke a bal oldali mutatónál kevesebb a kiválasztott forgatóponthoz képest, akkor a bal oldali mutatót balra mozgatjuk (+1-et adjunk hozzá), és addig ismételjük, amíg a bal oldali mutatónál nagyobbnak találjuk a a forgópont értéke vagy azzal egyenlő.
  • Ha az elem értéke a jobb oldali mutatónál a listán nagyobb, mint a pivot elem értéke, akkor a jobb oldali mutatót balra állítjuk. Addig ismételje ezt, amíg a jobb oldali mutató értéke alacsonyabb (vagy azzal egyenlő) a pivot értékével.
  • Ha a bal oldali mutató értéke kisebb vagy egyenlő a jobb oldali mutató értékével, cserélje ki az értékeket.
  • Mozgassa a jobboldali mutatót balra, balra, a balit jobbra.
  • Addig ismételje meg, amíg a bal és a jobb mutatók nem találkoznak.

Kód:

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

Kimenet:

5. Beszúrási rendezési algoritmus

A végrehajtás megkönnyítése érdekében az inkorporációs fajtát széles körben ismerték, mint az egyik egyszerűbb algoritmust. A beszúrási sorrendben a tömb elemeit összehasonlítják egymással, majd elrendezik egy meghatározott sorrendben. Ez nagyon hasonlít a kártyák pakliba rendezéséhez. A névbeillesztési rendezés abból a folyamatból származik, amikor egy elemet kiválaszt, azt a megfelelő helyre helyezi, majd az összes elemre megismétli.

Az algoritmus így működik:

  • A tömb első elemét már rendezettnek tekintik.
  • Válassza ki a tömb következő elemét.
  • Hasonlítsa össze a kiválasztott elemet a tömb összes elemével.
  • Tolja el a tömb minden elemét, amely nagyobb, mint a kiválasztott elem értéke.
  • Helyezze be az elemet
  • Ismételje meg a 2–5. Lépést, amíg a tömb rendezettségbe nem kerül.

Kód:

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

Kimenet:

6. Halom rendezési algoritmus

A halom rendezése az elemek rendezésének módja a „Halom” adatszerkezet felhasználásával. A módszer meglehetősen hasonlít a korábban tárgyalt szelekciós rendezési technikához. Most az a kérdés, hogy vajon mi a halom és hogyan definiálják őket, mielőtt az algoritmusba jutnánk, először megértjük a halom elemeit.

Dióhéjban egy halom egy bináris fa, néhány hozzáadott szabályokkal. Az egyik szabály kimondja, hogy a halomban lévő fának teljes bináris fának kell lennie, amely egyszerűen azt jelenti, hogy az összes csomópontot meg kell tölteni az aktuális szinten, mielőtt újabb hozzáadódna. A halom következő szabálya, hogy meghatározott gyerek és szülő kapcsolatnak kell lennie a halom elemértékeivel.

Min-halom esetén a szülő értékének kisebbnek kell lennie, mint gyermekeinek. Egy maximális halomban, amint kitalálhatja, a szülő értékének nagyobbnak kell lennie, mint gyermekének.

Most, hogy a definíciók nem megfelelőek, nézzük meg, hogyan működik a halomkészlet:

  • Először egy max halomot építünk, amely megbizonyosodik arról, hogy a legmagasabb értékű elem tetején van.
  • A felső elemet átváltjuk a halom utolsó elemével, eltávolítjuk a felső elemet a halomból és tároljuk egy válogatott tömbbe.
  • Az első és a második lépést addig ismételjük, amíg csak egy elem marad meg a halomban.

Egy dolog, amelyet figyelembe kell venni, hogy a Heaps nem támogatott natívan a JavaScripten, ezért törekednünk kell a Heaps tömbökkel történő megvalósítására. A halomfajták térbeli bonyolultsága O (1), amely kiváló, és bár a megértés és a megvalósítás szempontjából kissé bonyolultabb az egyesítési vagy beszúrási rendezéshez képest, azt gondolom, hogy a teljesítmény előnyei szempontjából végül jobb nagy projektek.

Kód:

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

Kimenet:

Következtetés

A válogatás fontos részét képezi az alkalmazások és weboldalak létrehozásának a JavaScript használatával. Most, hogy ismeri a munka elvégzéséhez szükséges legfontosabb algoritmusokat, jobban bíznod kell a JS Development programot.

Egy fontos tény, amelyet szem előtt kell tartani a különféle válogatásokkal kapcsolatban, az, hogy nem kell igazán sokat stressztelnie arra vonatkozóan, hogy milyen algoritmust használjon a legtöbb esetben. Most, hogy a számítógépes hardver annyira hatalmas, a modern telefon- és asztali processzorok nem tesznek elegendő izzadást, akár néhány milliszekundum alatt akár több száz elem rendezése is lehet. Csak azokban az esetekben, amikor ragaszkodik a lassú hardverhez, vagy olyan helyzetekben, amikor optimalizálja a kód minden egyes szakaszát, amikor a rendezési algoritmusok megváltoztatása hasznos lehet.

Ajánlott cikkek

Ez egy útmutató az algoritmusok rendezéséhez a JavaScript-ben. Itt tárgyaljuk a javascript-ben szereplő 6 legáltalánosabb algoritmust, valamint példákat és a kód megvalósítását. A következő cikkeket is megnézheti további információkért -

  1. JavaScript fordító
  2. Fordítva a JavaScript-ben
  3. Bevezetés a JavaScript-be
  4. Négyzetek a Java-ban
  5. Gyors rendezési algoritmusok a Java-ban
  6. Tömbök az adatszerkezetben
  7. C ++ algoritmus | Példák a C ++ algoritmusra

Kategória:

Szoftverfejlesztés