Az adatlisták rendezése nagyon fontos része az alkalmazásokban történő feldolgozásnak.
Hasznos adatok megjelenítéséhez és keresésekhez. Ezért nem meglepő, hogy minden jó szoftvermérnök tudja, hogyan kell rendezni a tömböket. Ez a cikk a JavaScript tömbök rendezésének néhány leggyakoribb algoritmusát ismerteti.
Tartalomjegyzék
Mi a válogatás, és miért hasznos?
Forrás: Unsplash
A rendezés az értékek szisztematikus rendszerezése valamilyen sorrend szerint. Ez a sorrend lehet csökkenő vagy növekvő. A tömbök JavaScriptben való rendezése hasznos, mivel lehetővé teszi az adatok értelmesebb megjelenítését.
Előfordulhat például, hogy egy személy először a legfrissebb fájlokkal rendezve szeretné látni a fájlokat, vagy a termékeket ár szerint rendezve. Hasznos az adatokon végzett bináris kereséshez is, amely csak rendezett adatokkal működik.
Bár vannak olyan funkciók és könyvtárak, amelyek segítik az adatok egyszerű rendezését, még mindig tudnia kell, hogyan működik a rendezés az interjúk kódolásához vagy amikor alacsony szintű kódot kell írnia.
JavaScript tömb rendezési algoritmusok
Buborékos rendezés
A Bubble Sort vitathatatlanul a legkönnyebben megérthető és megvalósítható algoritmus. Úgy működik, hogy egy lépésben végighurkolja a tömböt. Minden lépésnél végighaladunk a tömbön, az elejétől a végéig, összehasonlítva két szomszédos elemet. Ha az elemek rossz sorrendben vannak, akkor felcseréljük őket.
n lépést hajtunk végre, ahol n a tömb elemeinek száma. Minden lépésnél a tömb jobbról indulva rendeződik. A számokat növekvő sorrendbe rendező algoritmus pszeudokódja a következő:
1. Let n be the number of elements in the array 2. Loop n times, keeping count of the loops using i (doing the following in each loop) a. loop the array from the second element to the (n - i)th element b. if the previous element is greater than the current element, swap them.
JavaScriptre fordítva a kód így néz ki:
function sort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
Hogy jobban megértsük, mi történik, azt javaslom, hogy adjon hozzá egy console.logs fájlt a két cikluson belül, hogy megnézze, hogyan változik a tömb minden egyes lépéssel.
Az alábbi kódban módosítottam a rendezési függvényt úgy, hogy a console.logs fájlt hozzáadja a két cikluson belülre. Létrehoztam egy kis rendezetlen tömböt is, amelyet a rendezés funkcióval rendeztem.
function sort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
console.log(`Pass: ${i}`);
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
console.log(arr);
}
}
return arr;
}
const array = [9, 2, 7, 4, 1];
sort(array);
console.log(array);
A fenti kód futtatásának eredménye a következő lenne:
A buborékok rendezésének Big O időbeli összetettsége O(n ^ 2). Ennek az az oka, hogy n lépést hajt végre, amely minden egyes lépésnél áthalad a tömbön. Ezért nem skálázódik jól. Azonban a térkomplexitása O(1), mivel a helyükön módosítja a tömbelemeket.
Beszúrás rendezése
A beillesztési rendezés egy népszerű JavaScript tömbrendezési algoritmus. Tegyük fel, hogy beszúrási rendezést használunk az értékek növekvő sorrendbe rendezésére. Az algoritmus úgy működik, hogy kiválaszt egy számot, amelyet számnak nevezünk. Ezután a num-ot balra mozgatja, amíg a num-tól balra lévő összes többi szám kisebb lesz, mint num. Ha ez a második elemtől a végéig történik, minden szám rendezve lesz. Itt van egy leírás pszeudokódban.
1. Let n be the number of elements in the array
2. Loop i from 1 to n - 1 (start from the second element)
a. Set currentElement to array[i]
b. Set j to i - 1
c. While j >= 0 and array[j] > current_element
i. Move array[j] to array[j+1]
ii. Decrement j by 1
d. Set array[j+1] to current_element
És most, a JavaScriptben megvalósított pszeudokód a következő.
function insertionSort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const currentElement = array[i];
let j = i - 1;
while (j >= 0 && array[j] > currentElement) {
array[j + 1] = array[j];
j -= 1;
}
array[j + 1] = currentElement;
}
return array;
}
A Bubble Sorthez hasonlóan a console.logs hozzáadása segít elképzelni, mi történik. Az alábbi kódrészlet a beillesztési rendezést mutatja a munka közben.
function sort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const currentElement = array[i];
let j = i - 1;
console.log("Placing element:", currentElement);
while (j >= 0 && array[j] > currentElement) {
array[j + 1] = array[j];
j -= 1;
}
array[j + 1] = currentElement;
console.log("Placed it at position:", j + 1);
console.log(array);
}
return array;
}
const array = [4, 1, 2, 5, 3];
sort(array);
A fenti részlet futtatása pedig a következő eredményt adja:
Összevonási rendezés
Míg a beszúrásos rendezés és a buborékos rendezés skála négyzetes időben, az összevonási rendezés kvázi lineáris időben. Időbonyolultsága O(n * log(n)).
Az összevonási rendezés az oszd meg és uralkodj stratégiát alkalmazza. A tömb ismételten fel van osztva kisebb, egy-egy elemből álló tömbökre. A felosztás után ezeket visszaolvasztják.
Az osztás rekurzív, így a tömb később újra összeállítható.
A tömb visszaolvasztásakor az altömbök sorrendben egyesülnek. Az egyesítés ugyanúgy történik, mint egy rendezett tömb összevonása. Az ehhez szükséges pszeudokód az alábbiakban található:
1. If the length of the array is 1 or less, return the array (base case)
2. Find the middle index:
a. Set mid to the floor of (length of the array / 2)
3. Divide the array into two subarrays:
a. Create leftArray and copy the first half of the array into it (from index 0 to mid)
b. Create rightArray and copy the second half of the array into it (from index mid+1 to the end)
4. Recursively call MergeSort on leftArray
5. Recursively call MergeSort on rightArray
6. Merge the two sorted subarrays:
a. Create an empty resultArray
b. While both leftArray and rightArray are not empty:
i. If the first element in leftArray is less than or equal to the first element in rightArray, append it to resultArray
ii. Otherwise, append the first element in rightArray to resultArray
c. Append any remaining elements in leftArray to resultArray (if any)
d. Append any remaining elements in rightArray to resultArray (if any)
7. Return resultArray
A JavaScript-ben való implementálása a következőket eredményezné:
function sort(array) {
// Base case in which we stop subdividing the array
if (array.length == 1) {
return array;
}
// Finding the middle point of the array
const m = Math.round(array.length / 2);
// Divide the array into two halves
const leftUnsorted = array.slice(0, m);
const rightUnsorted = array.slice(m);
// Recursively call merge sort
const leftSorted = sort(leftUnsorted);
const rightSorted = sort(rightUnsorted);
// Return a merged sorted array
return merge(leftSorted, rightSorted);
}
function merge(left, right) {
// Merge two sorted lists
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex += 1;
} else {
result.push(right[rightIndex]);
rightIndex += 1;
}
}
return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}
Ha a kódot egy példatömbbel futtatja, akkor működnie kell.
Gyors rendezés
A Merge Sorthez hasonlóan a Gyorsrendezés is az oszd meg és uralkodj stratégián alapul. Az algoritmus kiválaszt egy pivot elemet. Ezután minden, a forgáspontnál nagyobb elemet jobbra mozgat, és balra kisebb, mint a forgáspont. Ha ez megtörtént, a forgócsap a megfelelő pozícióba kerül.
A pivot körüli elemek mozgatásához az algoritmus a pivot mozgatásával kezdődik a tömb végére.
Áthelyezés után egy mutatót használunk, hogy a tömb bal oldaláról hurkoljunk, és keressük a pivotnál nagyobb első számot. Ezzel egyidejűleg egy másik mutatóhurkot használunk a tömb jobb oldalán, és a pivotnál kisebb első számot keressük. Miután mindkét számot azonosítottuk, felcseréljük őket. Ezt az eljárást addig ismételjük, amíg a bal oldali mutató nagyobb nem lesz, mint a jobbra mutató.
Amikor megállunk, a pivottal utoljára felcserélt két szám közül a nagyobbat felcseréljük. Ezen a ponton a forgócsap a megfelelő helyzetben lesz; a pivotnál kisebb számok balra, míg a nagyobbak jobbra lesznek.
Ezt az eljárást rekurzívan megismételjük a pivottól balra és jobbra lévő altömbök esetében, amíg az altömböknek már csak egy eleme marad.
Íme a pszeudokód a gyors rendezéshez:
1. If lessThanPointer is less than greaterThanPointer:
a. Choose a pivot element from the array
b. Move elements such that elements less are to the left and elements greater are to the right:
c. Recursively call Quicksort on leftSubarray
d. Recursively call Quicksort on rightSubarray
És konvertáld JavaScriptre:
function sort(array, low, high) {
if (low < high) {
// Choose the pivot index and partition the array
const pivotIndex = move(array, low, high);
// Recursively sort the subarrays to the left and right of the pivot
sort(array, low, pivotIndex - 1);
sort(array, pivotIndex + 1, high);
}
}
function move(array, low, high) {
// Select the pivot element (in this case, the last element)
const pivotElement = array[high];
// Initialize the index for the smaller element
let i = low - 1;
for (let j = low; j < high; j++) {
// If the current element is less than or equal to the pivot, swap it with the element at index i+1
if (array[j] <= pivotElement) {
i += 1;
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// Swap the pivot element into its correct position
const temp = array[i];
array[i] = array[j];
array[j] = temp;
// Return the index of the pivot element
return i + 1;
}
Példatömb rendezése a Node.js gyorsrendezésével a következőket eredményezi:
A legjobb esetben a Quicksort kvázi lineáris időbonyolításban fut. A gyorsrendezésben a helyhasználat logaritmikusan is skálázódik. Ezért viszonylag hatékony a többi JavaScript tömbrendezési algoritmushoz képest.
Tippek a kódolási interjúkhoz
❇️ A gyakorlás a legfontosabb. Segít a különböző algoritmusok elsajátításában, de ami még fontosabb, segít a problémamegoldó és a számítási gondolkodási készség fejlesztésében. Olyan platformokon is gyakorolhatsz, mint pl Leetcode és AlgoExpert.
❇️ Először próbáld meg megoldani a problémát. Ahelyett, hogy egyenesen a megoldásra ugorna, próbálja meg megoldani, mert segít fejleszteni problémamegoldó készségeit.
❇️ Ha egy probléma túl sokáig tart, ugorjon a megoldáshoz; a megoldásból még meg lehet tanulni a probléma megoldását. A legtöbb tanulási platform megoldást kínál. A ChatGPT vagy a Google Bard szintén hasznos a fogalmak magyarázatához.
❇️ Ezenkívül ne írjon azonnal kódot; táblázzon fel megoldásait, és gondolja át őket, mielőtt kódot írna. A pszeudokód az ötletek gyors lejegyzésének is hasznos módja.
Következtetés
Ebben a cikkben a legnépszerűbb rendezési algoritmusokkal foglalkoztunk. Mindezek megtanulása azonban elsőre nyomasztónak tűnhet. Ezért általában azt javaslom, hogy ahelyett, hogy egyetlen forrásra támaszkodnánk, keverjük össze a különböző forrásokat. Boldog kódolást!
Ezután nézze meg a rendezett függvény megértését a Pythonban.