Úvod do vkladania Zoradiť do JavaScriptu
Triedenie je jedným z dôležitých konceptov, ktoré sa programátori naučia začať svoju cestu v informatike bez ohľadu na to, aký programovací jazyk sa vybrali na štúdium. Zoradenie nám pomáha lokalizovať cieľové údaje, ktoré chceme prehľadávať, rýchlejšie a pohodlnejšie ich usporiadaním vzostupne alebo zostupne.
Algoritmy triedenia sa používajú na zmenu poradia prvkov, pričom prvkom môže byť číslo alebo reťazec. Existuje mnoho typov triediacich algoritmov na základe ich spôsobu triedenia a prístupu, ktorý používajú na triedenie prvkov, a každý typ má svoje výhody a nevýhody.
V tomto blogu sa zameriame na druh vkladania, bežný druh, ktorý je ľahko zrozumiteľný a implementovateľný.
Čo je to vkladanie v JavaScripte?
Zoradenie vloženia je jednoduchý, ľahko zrozumiteľný algoritmus, ktorý najlepšie funguje s malým zoznamom údajov zoradením každého prvku v zozname údajov jeden po druhom zľava doprava. Nazýva sa aj porovnávacie zoradenie, pri ktorom porovnáva aktuálnu hodnotu s ostatnými hodnotami v rovnakom zozname údajov, ktorý sa triedi. Podľa iteračného prístupu je každý prvok zaradený do zoznamu údajov v správnom poradí.
Čím viac času trvá algoritmus na triedenie, jeho výkon sa považuje za zlý a je potrebné zvážiť iný algoritmus na triedenie údajov. Zoradenie vloženia má časovú zložitosť O (n²) alebo beží kvadratický čas na zoradenie zoznamu údajov v najhoršom prípade. Zvyčajne to nie je príliš efektívne a nemalo by sa používať pre veľké zoznamy. Zvyčajne však prevyšuje pokročilé algoritmy, ako je napríklad rýchly prenos alebo zlučovanie na menších zoznamoch.
Vkladanie triedenia je väčšinou efektívnejšie ako iné algoritmy kvadratického triedenia, ako je triedenie bubliniek alebo triedenie výberu. Jeho najlepší prípad je čas O (n) alebo lineárny, ku ktorému dôjde, ak je vstupné pole už zoradené. V priemere je doba vykonávania triedenia stále kvadratická.
V nižšie uvedenom príklade budeme mať ľahký prístup na vysokej úrovni na triedenie údajov uložených v štruktúre dát poľa a na triedenie údajov použijeme metódu triedenia bez zavedenia akýchkoľvek algoritmov.
Príklad - Algoritmus usporiadania vloženia
kód:
// Declaring unsorted data and storing it in array data structure
var dataArray = (96, 5, 42, 1, 6, 37, 21) // Function - Insertion Sort Algo.
function insertSort(unsortedData) (
for (let i = 1; i < unsortedData.length; i++) (
let current = unsortedData(i);
let j;
for(j=i-1; j >= 0 && unsortedData(j) > current;j--) (
unsortedData(j + 1) = unsortedData(j) )
unsortedData(j + 1) = current;
)
return unsortedData;
)
// print sorted array
console.log(insertSort(dataArray));
Výkon:
Vysvetlenie: V algoritme sme implementovali 2 pre slučky, vonkajší pre slučku je iterovaný cez prvky poľa a vnútorný pre slučku sa používa na triedenie prvkov poľa vo vzostupnom poradí podľa ich hodnoty. Aktuálna premenná obsahuje aktuálnu hodnotu poľa a premenná j je nastavená na jednu hodnotu menšiu ako aktuálna pozícia indexu poľa. Skontrolujeme, či je aktuálny prvok (prúd) menší ako hodnota poľa na j- tej pozícii (unsortedData (j) ) a ak je pravdivý, potom tieto hodnoty zoradíme.
Iterácia 1 - súčasná (96): (96, 5, 42, 1, 6, 37, 21)
Iterácia 2 - súčasná (5): (5, 96, 42, 1, 6, 37, 21)
Iterácia 3 - súčasná (42): (5, 42, 96, 1, 6, 37, 21)
Iterácia 4 - súčasná (1): (1, 5, 42, 96, 6, 37, 21)
Iterácia 5 - súčasná (6): (1, 5, 6, 42, 96, 37, 21)
Iterácia 6 - súčasná (37): (1, 5, 6, 37, 42, 96, 21)
Iterácia 7 - súčasná (21): (1, 5, 6, 21, 37, 42, 96)
Vonkajší cyklus na opakovanie slučky začína na 1. pozícii indexu, pretože chceme presunúť najmenší prvok na ľavú stranu, takže porovnávame, či je aktuálny prvok menší ako prvky na jeho ľavej strane.
Druhy triedenia
Typy algoritmov, ktoré sa používajú na triedenie údajov, zahŕňajú nasledujúce koncepty alebo nápady v ich prístupe k triedeniu údajov:
- Porovnanie so stratégiami bez porovnania,
- Iteratívna verzus rekurzívna implementácia,
- Paradigma rozdelenia a dobytia (to alebo ono),
- Náhodný prístup.
Pozrime sa na niekoľko príkladov:
1. Zlúčiť zoradenie používa prístup triedenia a zdolávania k triedeniu prvkov v poli.
2. Zoradenie vloženia, triedenie bubliniek je zoradenie založené na porovnaní.
Keď sú dáta triedené, je ľahšie prísť s optimálnym riešením zložitých problémov. napríklad,
- Hľadanie konkrétnej hodnoty,
- Nájdenie minimálnej alebo maximálnej hodnoty,
- Testovanie jedinečnosti a odstránenie duplikátov,
- Počítanie, koľkokrát sa konkrétna hodnota objavila, atď.
záver
V tomto článku sme prešli definíciou typu inzercie a jej časovou zložitosťou a rôznymi ďalšími typmi algoritmov triedenia na základe ich prístupu. Štúdium rôznych triediacich algoritmov nám pomáha určiť, ktorý z nich je za určitých okolností vhodnejší, alebo použiť prípady, ktoré nám pomáhajú triediť údaje rýchlejšie.
Odporúčané články
Toto je sprievodca triedením vkladania v JavaScripte. Tu diskutujeme o tom, čo je vkladanie v javascripte a jeho typy s príkladom. Ďalšie informácie nájdete aj v nasledujúcich článkoch -
- Vzory v JavaScripte
- Prípad v jazyku JavaScript
- Podmienené vyhlásenia v JavaScripte
- Objekty JavaScript
- Rôzne typy slučiek s jej výhodami