Třídění seznamů dat je tak zásadní součástí zpracování v aplikacích.
Je to užitečné pro zobrazování dat a provádění vyhledávání. Není proto žádným překvapením, že každý dobrý softwarový inženýr by měl vědět, jak třídit pole. Tento článek vysvětluje některé z nejběžnějších algoritmů pro řazení polí v JavaScriptu.
Table of Contents
Co je třídění a proč je užitečné?
Zdroj: Unsplash
Třídění je systematické uspořádání hodnot podle nějakého řádu. Toto pořadí může být sestupné nebo vzestupné. Řazení polí v JavaScriptu je užitečné, protože umožňuje smysluplnější zobrazení dat.
Někdo si například může přát vidět nejprve soubory seřazené podle nejnovějších souborů nebo produkty seřazené podle ceny. Je také užitečné pro provádění binárního vyhledávání dat, které pracuje pouze s seřazenými daty.
I když existují funkce a knihovny, které vám pomohou snadno třídit data, stále potřebujete vědět, jak třídění funguje pod pokličkou pro rozhovory s kódováním nebo když musíte psát nízkoúrovňový kód.
Algoritmy řazení JavaScript Array
Bublinové řazení
Bubble Sort je pravděpodobně nejjednodušší algoritmus na pochopení a implementaci. Funguje to tak, že prochází polem v průchodu. Při každém průchodu se pohybujeme polem od začátku do konce a porovnáváme dva sousední prvky. Pokud jsou prvky ve špatném pořadí, vyměníme je.
Provedeme n průchodů, kde n je počet prvků v poli. Při každém průchodu se pole seřadí počínaje zprava. Pseudokód pro algoritmus pro řazení čísel ve vzestupném pořadí je následující:
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.
Při překladu do JavaScriptu by kód vypadal takto:
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;
}
Abyste lépe porozuměli tomu, co se děje, doporučuji přidat do dvou smyček soubor console.logs, abyste viděli, jak se pole mění s každým průchodem.
V níže uvedeném kódu jsem upravil funkci řazení tak, aby do dvou smyček přidala console.logs. Vytvořil jsem také malé netříděné pole, které jsem seřadil pomocí funkce řazení.
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);
Výsledkem spuštění výše uvedeného kódu by bylo:
Bublinové třídění má velkou časovou složitost O (n ^ 2). Je to proto, že provádí n průchodů, které procházejí polem při každém průchodu. Proto se špatně měří. Má však prostorovou složitost O(1), protože upravuje prvky pole na místě.
Řazení vkládání
Vložení řazení je populární algoritmus řazení pole JavaScriptu. Předpokládejme, že používáme řazení vložení k řazení hodnot ve vzestupném pořadí. Algoritmus funguje tak, že vybereme číslo, které budeme nazývat num. Potom posouvá num doleva, dokud každé druhé číslo nalevo od num nebude menší než num. Všechna čísla budou seřazena, pokud se tak stane od druhého prvku až do konce. Zde je popis v pseudokódu.
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
A nyní, pseudokód implementovaný v JavaScriptu je následující.
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;
}
Stejně jako u Bubble Sort vám přidání console.logs pomůže vizualizovat, co se děje. Níže uvedený úryvek kódu ukazuje řazení vkládání při práci.
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 spuštění úryvku výše vede k následujícímu výsledku:
Sloučit třídění
Zatímco řazení podle vložení a třídění podle bublin se měří v kvadratickém čase, řazení slučování měří v kvazilineárním čase. Má časovou složitost O(n * log(n)).
Sloučit řazení využívá strategii rozděl a panuj. Pole je opakovaně rozděleno na menší pole po 1 prvku. Po rozdělení jsou pak zpět sloučeny.
Dělení je rekurzivní, takže pole lze později znovu sestavit.
Při sloučení pole zpět se podpole sloučí v pořadí. Sloučení se provádí stejným způsobem, jako byste sloučili seřazené pole. Pseudokód k tomu je napsán níže:
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
Jeho implementace v JavaScriptu by přinesla následující:
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));
}
Pokud kód spustíte s ukázkovým polem, mělo by to fungovat.
Rychlé řazení
Stejně jako Merge Sort, i Quick Sort spoléhá na strategii rozděl a panuj. Algoritmus vybere prvek pivotu. Dále přesune všechny prvky větší než čep doprava a menší než čep doleva. Jakmile to uděláte, čep bude ve správné poloze.
Chcete-li přesunout prvky kolem pivotu, algoritmus začne přesunutím pivotu na konec pole.
Po jeho přesunutí použijeme ukazatel na smyčku zleva pole a hledáme první číslo větší než pivot. Současně použijeme další smyčku ukazatele zprava pole a hledáme první číslo menší než pivot. Jakmile jsou obě čísla identifikována, vyměníme je. Tento postup se opakuje, dokud není ukazatel zleva větší než ukazatel vpravo.
Když se zastavíme, prohodíme větší ze dvou naposledy prohozených čísel s pivotem. V tomto okamžiku bude čep ve správné poloze; čísla menší než pivot budou vlevo, zatímco čísla větší budou vpravo.
Tento postup se rekurzivně opakuje pro podpole nalevo a napravo od pivotu, dokud podpolím nezůstane pouze jeden prvek.
Zde je pseudokód pro rychlé řazení:
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
A převod na JavaScript:
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;
}
Řazení příkladu pole pomocí Quick Sort v Node.js by mělo přinést následující:
V nejlepším případě běží Quicksort v kvazilineární časové složitosti. Využití místa v rychlém řazení se také mění logaritmicky. Proto je relativně efektivní ve srovnání s jinými algoritmy řazení pole JavaScript.
Tipy pro vaše rozhovory o kódování
❇️ Praxe je klíčová. Pomáhá vám naučit se různé algoritmy, ale co je důležitější, pomáhá vám rozvíjet dovednosti při řešení problémů a výpočetní myšlení. Můžete také cvičit na platformách jako Leetcode a AlgoExpert.
❇️ Nejprve se pokuste problém vyřešit. Namísto toho, abyste skočili rovnou k řešení, zkuste je vyřešit, protože vám to pomáhá rozvíjet vaše schopnosti řešit problémy.
❇️ Pokud problém trvá příliš dlouho, přejděte k řešení; stále se můžete naučit řešit problém z řešení. Většina platforem pro výuku nabízí řešení. Pro vysvětlení pojmů se hodí i ChatGPT nebo Google Bard.
❇️ Také nepište kód okamžitě; prezentujte svá řešení a promyslete je před psaním kódu. Pseudokód je také užitečný způsob rychlého zapisování nápadů.
Závěr
V tomto článku jsme se zabývali nejpopulárnějšími třídicími algoritmy. Naučit se toto všechno se však může zpočátku zdát zdrcující. Proto obvykle doporučuji míchat různé zdroje namísto spoléhání se jen na jeden. Šťastné kódování!
Dále se podívejte na porozumění tříděné funkci v Pythonu.