Seřazovací algoritmy
V této části si ukážeme algoritmy, které slouží k seřazování. V JavaScriptu máme pro seřazování polí k dispozici metodu sort, občas se nám ale může hodit napsat si svoji vlastní a efektivnější. Podíváme se tu celkem na 6 seřazovacích algoritmů: bubble, selection, insertion, merge, quick a radix sort.
Bubble Sort
První seřazovací algoritmus, který si ukážeme je Bubble Sort. Tento algoritmus spočívá v tom, že se postupně projíždí celé pole a vždy se porovnávají dvě položky vedle sebe, které se podle podmínky prohodí nebo zůstanou tak jak jsou. Takto se pole projíždí tak dlouho, dokud se celé neseřadí.
function bubbleSort(pole) {
// tato proměnná bude určovat, jestli při posledním projíždění pole proběhly nějaké výměny
let noSwaps;
// pole se bude opakovaně projíždět od začátku po index i, který se bude postupně snižovat
for (let i = pole.length; i > 0; i--) {
noSwaps = true;
// pole se projede od začátku po index i
for (let j = 0; j < i - 1; j++) {
// tuto podmínku můžeme změnit podle toho, jak chceme položky v poli seřadit
if (pole[j] > pole[j+1]) {
// pokud je hodnota nalevo větší než hodnota napravo, tak se hodnoty vymění
let temp = pole[j];
pole[j] = pole[j+1];
pole[j+1] = temp;
// nastavíme, že jsme při tomto projíždění pole alespoň jednou změnili hodnoty
noSwaps = false;
}
}
// pokud při posledním projíždění pole neproběhly žádné výměny hodnot, pole je seřazené
if (noSwaps) break;
}
return pole;
}
const serazenePole = bubbleSort([25,5,30,24,10,8,40,28]);
console.log("Seřazené pole:");
console.log(serazenePole);Časová náročnost Bubble Sort algoritmu je O(n2). Samozřejmě záleží na tom, jak moc je seřazované pole již seřazené. U některých polí může proběhnout méně cyklů, u některých více.
Selection Sort
Teď si ukážeme Selection Sort. Tento algoritmus funguje tak, že se seřazené položky hromadí na začátku pole a při procházení pole se vždy najde nejmenší položka, která se k seřazeným položkám na konci cyklu přidá.
function selectionSort(pole) {
// tato proměnná bude uchovávat index na nejmenší položku pole v jednom cyklu
let nejmensi;
// pole se postupně projede od začátku po konec (index i bude ukončovat část pole, která je již seřazená)
for (let i = 0; i < pole.length; i++) {
// nastavení nejmenší hodnoty na index i
nejmensi = i;
// pole se projede od indexu i po konec pole
for (let j = i+1; j < pole.length; j++){
// pokud je položka menší než dosud nejmenší položka v tomto cyklu, tak se nastaví jako nejmenší
if (pole[j] < pole[nejmensi]) {
nejmensi = j;
}
}
// pokud byla nalezena položka, která je menší než položka na indexu i, tak se s ní prohodí
if (i !== nejmensi) {
// prohození hodnoty na indexu i s hodnotou na indexu nejmensi
let temp = pole[i];
pole[i] = pole[nejmensi];
pole[nejmensi] = temp;
}
}
return pole;
}
const serazenePole = selectionSort([25,5,30,24,10,8,40,28]);
console.log("Seřazené pole:");
console.log(serazenePole);Časová náročnost Selection Sort algoritmu je O(n2), ale narozdíl od Bubble Sort, který má časovou náročnost také O(n2), se položky přehazují jen po projetí pole.
Insertion Sort
Jako další seřazovací algoritmus si ukážeme Insertion Sort. Tento algoritmus funguje tak, že se prochází celé pole a vždy se každá položka zařadí směrem na začátek, kde se nachází již dříve seřazené položky.
function insertionSort(pole) {
// tato proměnná bude uchovávat hodnotu, která se bude zařazovat směrem na začátek pole
let aktualniHodnota;
// tento cyklus postupně projede všechny položky pole a zařadí je směrem na začátek
for (let i = 1; i < pole.length; i++) {
// uložení hodnoty, která se má zařadit směrem na začátek
aktualniHodnota = pole[i];
// proměnnou j pro následující cyklus deklarujeme již zde, abychom ji mohli použít i za cyklem
let j = i-1;
// následující cyklus se bude opakovat tak dlouho, dokud proměnná j nedojede na začátek pole,
// nebo nenajede na položku, která je menší nebo rovna hodnotě, která se zařazuje
for (; j >= 0 && pole[j] > aktualniHodnota; j--) {
// položka na kterou odkazuje proměnná j se posune o jednu položku doprava
pole[j+1] = pole[j];
}
// zařazovaná hodnota se umístí před posunuté položky
pole[j+1] = aktualniHodnota;
}
return pole;
}
const serazenePole = insertionSort([25,5,30,24,10,8,40,28]);
console.log("Seřazené pole:");
console.log(serazenePole);Časová náročnost Insertion Sort algoritmu je O(n2). Je vhodné jej použít na seřazování polí, která jsou již skoro seřazená.
Merge Sort
Tento algoritmus funguje tak, že se pole postupně dělí dokud nevzniknou pole o jedné položce, a ty se poté zase seskládají dohromady a pole se tak seřadí. Nebudu to tu v textu rozebírat, myslím že v interaktivní ukázce to pochopíte mnohem lépe. Nejdříve bych tu chtěl ale ještě ukázat funkci, která slouží ke spojení dvou seřazených polí, a zároveň zajišťuje aby byla pole i nadále seřazená. Samotná funkce provádějící Merge Sort algoritmus je docela krátká, ale využívá právě tuto funkci.
// tato funkce spojí dvě seřazená pole (vytvořené pole bude také seřazené)
function merge(pole1, pole2) {
// vytvoření pole, do kterého se předaná pole spojí
let vysledek = [];
let i = 0; // proměnná pro index pole1
let j = 0; // proměnná pro index pole2
// tento cyklus bude probíhat tak dlouho, dokud se jedno z polí celé neprojede
while (i < pole1.length && j < pole2.length) {
if (pole2[j] > pole1[i]) {
// pokud je položka v pole1 menší než v pole2, tak se přidá do pole vysledek
vysledek.push(pole1[i]);
// posunutí indexu i, který ukazuje na položky v pole1
i++;
} else {
// pokud je položka v pole2 menší než v pole1, tak se přidá do pole vysledek
vysledek.push(pole2[j]);
// posunutí indexu j, který ukazuje na položky v pole2
j++;
}
}
// pokud v pole1 zbyly nějaké položky, tak se přidají do pole vysledek
while (i < pole1.length) {
vysledek.push(pole1[i]);
i++;
}
// pokud naopak v pole2 zbyly nějaké položky, tak se přidají do pole vysledek
while (j < pole2.length) {
vysledek.push(pole2[j]);
j++;
}
return vysledek;
}
const pole = merge([6, 9, 51, 63, 70], [5, 8, 50, 52]);
console.log("spojená pole:");
console.log(pole);V přechozí ukázce jste mohli vidět funkci na sloučení dvou seřazených polí do jednoho seřazeného pole. Jak jsem již psal výše, Merge Sort algoritmus postupně dělí celé pole na pole o jedné položce. Dělá to, protože využívá toho, že pole o jedné položce je již seřazené. Na tato pole se tedy může postupně použít funkce, která je spojí dohromady a na konci nám vznikne seřazené pole.
Funkce provádějící Merge Sort používá rekurzy a může pro vás být obtížnější ji pochopit. Když jsem se ji učil já, tak jsem si tento algoritmus musel rozepsat na papír. Myslím ale, že následující ukázka vám může pochopení Merge Sort algoritmu dost usnadnit. Pod ukázku jsem přidal vizualizaci polí, takže při přehrávání ukázky víte, kde se co nachází a nemusíte si to někam psát, jako jsem to dělal já.
function merge(pole1, pole2) {
let vysledek = [];
let i = 0;
let j = 0;
while (i < pole1.length && j < pole2.length) {
if (pole2[j] > pole1[i]) {
vysledek.push(pole1[i]);
i++;
} else {
vysledek.push(pole2[j]);
j++;
}
}
while (i < pole1.length) {
vysledek.push(pole1[i]);
i++;
}
while (j < pole2.length) {
vysledek.push(pole2[j]);
j++;
}
return vysledek;
}
function mergeSort(pole) {
// pokud má pole jen jednu položku, tak jej funkce vrátí
if (pole.length <= 1) return pole;
// získání prostředního indexu pole
let middle = Math.trunc(pole.length/2);
// zavolání funkce mergeSort s levou částí pole
let left = mergeSort(pole.slice(0,middle)); // pole se zkopíruje od začátku po index middle
// zavolání funkce mergeSort s pravou částí pole
let right = mergeSort(pole.slice(middle)); // pole se zkopíruje od indexu middle po konec
// sloučení levé a pravé části pole pomocí funkce merge
return merge(left, right);
}
const serazenePole = mergeSort([25,5,30,24,10,8,40,28]);
console.log("Seřazené pole:");
console.log(serazenePole);Časová náročnost Merge Sort algoritmu je O(n log n). Narozdíl od předchozí algoritmů, to jak je pole již seřazené nemá žádný vliv, protože Merge Sort stejně celé pole rozdělí na více polí o jedné položce. U předchozích algoritmů jsme si ani neuváděli paměťovou náročnost, protože byla O(1). U Merge Sort to tak není, protože vytváříme nová pole a paměťová náročnost je tak O(n).
Quick Sort
Jako další seřazovací algortimus si ukážeme Quick Sort. Stejně jako Merge Sort používá pomocnou funkci. Jejím úkolem je v předaném poli (nebo jeho části) určit položku, před kterou se umístí ostatní položky pole, které jsou menší než tato položka. Index této položky se na konci funkce vrátí, říká se mu pivot. Funkce tedy uřčí pivot, před něj umístí menší položky, za ním zůstanou větší položky a pivot vrátí. Jako pivot se vždy vybere první položka předaného pole (nebo jeho části). Existuje také Random Quick Sort algoritmus, který pivot vybere náhodně, ale ten si tu ukazovat nebudeme.
Stejně jako u Merge Sort se pojďme nejprve podívat na pomocnou funkci pivot:
// pomocná funkce pro prohození dvou položek v poli
function swap(pole, index1, index2) {
const temp = pole[index1];
pole[index1] = pole[index2];
pole[index2] = temp;
};
// tato funkce uřčí pivot, před něj umístí menší položky a pivot vrátí
// funkce přijímá volitelné parametry start a konec, které určují, v jaké části pole má funkce pracovat
function pivot(pole, start = 0, konec = pole.length - 1) {
// jako pivot hodnotu nastavíme položku na indexu start (na začátku pole)
let pivot = pole[start];
// vytvoření swap indexu, který bude sloužit k výměně menších položek než je pivot hodnota
let swapIdx = start;
// pole se projede od začátku po konec (od indexu start po index konec)
for (let i = start + 1; i <= konec; i++) {
// pokud je pivot hodnota větší než porovnávaná položka pole, tak se zvýší
// swap index a položka na kterou ukazuje se prohodí s porovnávanou položkou
if (pivot > pole[i]) {
swapIdx++;
swap(pole, swapIdx, i);
}
}
// vyměnění pivot položky s položkou, na kterou ukazuje swap index
swap(pole, start, swapIdx);
// funkce vrátí pivot index
return swapIdx;
}
const pole = [4,8,2,1,5,7,6,3];
console.log("Pole před zavoláním funkce pivot:");
console.log(pole);
// funkce pivot sice vrací index, ale pole, které jí předáváme modifikuje (protože pole jsou objekty a předávají se adresou)
const pivotIndex = pivot(pole);
console.log(`Pivot: ${pivotIndex} (první položka se přesunula na index ${pivotIndex} a před ni se umístili ostatní menší položky)`);
console.log("Pole po zavolání funkce pivot:");
console.log(pole);Když už jsme si ukázali funkci pivot, kterou Quick Sort používá, tak se můžeme podívat na samotný Quick Sort algoritmus. Stejně jako Merge Sort používá rekurzy, takže pro vás může být trochu těžší na pochopení. Funguje tak, že se postupně volá funkce pivot se stále menší částí pole až se nakonec pole seřadí. Na začátku se pole rozdělí na dvě poloviny. Jedna polovina bude obsahovat menší položky a druhá větší. Poté se první polovina opět rozdělí na dvě části, a první část opět bude obsahovat menší hodnoty. Tak se to stále opakuje až se mergeSort funkce nakonec zavolá s částí, která neobsahuje žádné položky a začne stejný proces postupně pro dříve rozdělené pravé části pole. Z tohoto textu toho asi nic moc nechápete, spíš vám to pomůže pochopit následující ukázka.
function swap(pole, index1, index2) {
const temp = pole[index1];
pole[index1] = pole[index2];
pole[index2] = temp;
};
function pivot(pole, start = 0, konec = pole.length - 1) {
let pivot = pole[start];
let swapIdx = start;
for (let i = start + 1; i <= konec; i++) {
if (pivot > pole[i]) {
swapIdx++;
swap(pole, swapIdx, i);
}
}
swap(pole, start, swapIdx);
return swapIdx;
}
function quickSort(pole, left = 0, right = pole.length -1) {
// pokud je v části pole určená proměnnými left a right nějaká hodnota, tak bude funkce quickSort pokračovat
if (left < right) {
// zavolání funkce pivot, která část pole rozdělí (spíš předělá) na dvě části a vrátí pivot index
// (v levé části pole budou menší položky než pivot a na pravé části budou větší položky než pivot)
let pivotIndex = pivot(pole, left, right);
// zavolání funkce quickSort s levou částí pole (nebo levou částí části pole)
quickSort(pole, left, pivotIndex-1); // (parametr left bude left a parametr right bude pivotIndex-1)
// zavolání funkce quickSort s pravou částí pole (nebo pravou částí části pole)
quickSort(pole, pivotIndex+1, right); // (parametr left bude pivotIndex+1 a parametr right bude right)
}
return pole;
}
const serazenePole = quickSort([25,5,30,24,10,8,40,28]);
console.log("Seřazené pole:");
console.log(serazenePole);Doufám že vám předchozí interaktivní ukázka pomohla Quick Sort algortimus pochopit. Je to podle mě asi nejtěžší seřazovací algoritmus, který je v této části ukázaný.
Čásová náročnost Quick Sort algoritmu je O(n log n). Ale záleží na seřazovaném poli, pokud nám bude funkce pivot například pořád vracet index 0, tak je to O(n2). Quick Sort sice pracuje jen s polem, který mu předáme, ale jeho paměťová náročnost je kvůli rekurzy O(log n).
Radix Sort
Jako poslední seřazující algoritmus si ukážeme Radix Sort. Jde o speciální algoritmus, který nikdy neporovnává hodnoty mezi položkami pole. Využívá faktu, že větší číslo je zapsáno s více číslicemi.
Pro vytvoření Radix Sort algoritmu potřebujeme pár pomocných funkcí. Potřebujeme funkci, pomocí které získáme potřebnou číslici z předaného čísla a funkci na získání největšího počtu číslic nějakého čísla v poli. Funkce, které potřebujeme ukazuje následující ukázka. Vůbec nemusíte zkoumat jak fungují, kdybyste je potřebovali, tak si je můžete najít na Stack Overflow nebo někde jinde. Důležité je jen abyste věděli k čemu slouží.
// tato funkce vrací požadovanou číslici z předaného čísla
function ziskatCislici(cislo, i) {
return Math.floor(Math.abs(cislo) / Math.pow(10, i)) % 10;
}
// pomocná funkce pro funkci nejviceCislic
function pocetCislic(cislo) {
if (cislo === 0) return 1;
return Math.floor(Math.log10(Math.abs(cislo))) + 1;
}
// tato funkce vrací největší počet číslic čísla v předaném poli
function nejviceCislic(cisla) {
let nejvice = 0;
// pole cisla se postupně projede a zjistí se největší počet číslic nějakého čísla v poli
for (let i = 0; i < cisla.length; i++) {
// metoda Math.max vrátí největší číslo z předaných čísel
nejvice = Math.max(nejvice, pocetCislic(cisla[i]));
}
return nejvice;
}
console.log("První číslice čísla 321: " + ziskatCislici(321, 2));
console.log("Druhá číslice čísla 321: " + ziskatCislici(321, 1));
console.log("Třetí číslice čísla 321: " + ziskatCislici(321, 0));
console.log("Nejvíce číslic čísla v poli [2,43,1,348]: " + nejviceCislic([2,43,1,348]));> Druhá číslice čísla 321: 2
> Třetí číslice čísla 321: 1
> Nejvíce číslic čísla v poli [2,43,1,348]: 3
>
Pro Radix Sort jsem interaktivní ukázku nevytvořil. Pokud chcete tento algoritmus vizuálně vidět, tak doporučuji stránku VisuAlgo. Zde vám jen ukážu okomentovaný kód:
function radixSort(cisla) {
// získání maximálního počtu číslic
let maxPocetCislic = nejviceCislic(cisla);
// postupně se pole bude procházet pro každou číslici (pozici číslice určuje k)
for (let k = 0; k < maxPocetCislic; k++) {
// vytvoření pole o 10 polích (každé pole bude ukládat čísla pro jednu číslici na určitém místě čísla)
let digitBuckets = Array.from({length: 10}, () => []);
// postupně se projede celé pole cisla
for (let i = 0; i < cisla.length; i++) {
// získání číslice na pozici k
let cislice = ziskatCislici(cisla[i], k);
// vložení čísla do pole podle číslice
digitBuckets[cislice].push(cisla[i]);
}
// sloučení polí v digitalBuckets do jednoho pole pomocí metody concat
// (pole s čísly s číslicemi 0 se sloučí na začátek a pole s čísly s číslicemi 9 se sloučí na konec);
cisla = [].concat(...digitBuckets); // použití spread operátoru na digitalBuckets (jednotlivá pole se rozmístí jako argumenty funkce)
}
return cisla;
}
const serazenePole = radixSort([25,5,30,24,10,8,40,28]);
this.console.log("Seřazené pole:");
this.console.log(serazenePole);> [5,8,10,24,25,28,30,40]
>
Časová náročnost Radix Sort algoritmu je O(nk) a paměťová náročnost je O(n+k).
V této části jsme si ukázali 6 různých seřazovacích algoritmů. Možná teď ale nevíte, který se kdy hodí použít. S tím vám může pomoct tato stránka, na které si můžete otestovat rychlost různých seřazovacích algoritmů na různá pole. Můžete si tam například zvolit, že chcete vidět jak rychle algoritmy seřadí skoro seřazené pole, obráceně seřazené pole, a tak podobně.