Introducere în sortarea inserției în JavaScript
Sortarea este unul dintre conceptele importante pe care programatorii învață să-și înceapă călătoria în informatică indiferent de limbajul de programare selectat pentru a învăța. Sortarea ne ajută să localizăm datele țintă pe care dorim să le căutăm într-o manieră mai rapidă și convenabilă, prin sortarea lor în ordine crescătoare sau descendentă.
Algoritmii de sortare sunt folosiți pentru a reordona elemente, unde un element poate fi un număr sau un șir. Există multe tipuri de algoritmi de sortare bazate pe metoda lor de sortare și pe abordarea pe care o urmează pentru a sorta elementele, iar fiecare tip are avantajele și dezavantajele sale.
În acest blog, ne vom concentra pe sortarea de inserție, un tip comun care este ușor de înțeles și de implementat.
Ce este sortarea inserției în JavaScript?
Sortarea inserției este un algoritm simplu, ușor de înțeles care funcționează cel mai bine cu o listă de date mică, sortând fiecare element din lista de date unul câte unul de la stânga la dreapta. Este, de asemenea, cunoscut ca un sort de comparație în care comparează valoarea curentă cu celelalte valori din aceeași listă de date care este sortată. Urmează o abordare iterativă pentru a plasa fiecare element în ordinea corectă în lista de date.
Cu cât un algoritm necesită mai mult timp pentru a sorta, se spune că performanțele sale sunt proaste și trebuie să ia în considerare un alt algoritm pentru a sorta datele. Sortarea de inserare are o complexitate de timp de O (n²) sau execută o perioadă patratică pentru a sorta lista de date în cel mai rău caz. În mod obișnuit, acest lucru nu este foarte eficient și nu ar trebui utilizat pentru liste mari. Cu toate acestea, de obicei, depășește algoritmi avansați, precum quicksort sau mergesort pe liste mai mici.
Sortarea inserției, de cele mai multe ori este mai eficientă decât alți algoritmi de sortare quadratici, cum ar fi sortarea cu bule sau sortarea selecției. Cel mai bun caz al său, timpul este O (n) sau liniar, care apare dacă matricea de intrare este deja sortată. În medie, timpul de execuție al sortării de inserție este încă cuadrat.
În exemplul de mai jos vom avea o abordare ușoară la nivel înalt pentru a sorta datele stocate într-o structură de date matricială și vom folosi metoda de sortare pentru a sorta datele fără a implementa niciun algoritm.
Exemplu - Algoritm sortare inserție
Cod:
// 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));
ieşire:
Explicație: În algoritm, am implementat 2 pentru bucle, exteriorul pentru buclă este de a itera peste elementele de matrice, iar interiorul pentru buclă este folosit pentru a sorta elementele de matrice în ordinea crescătoare a valorii lor. Variabila curentă păstrează valoarea curentă a tabloului și variabila j este setată la o valoare mai mică decât poziția indexului curent al tabloului. Verificăm dacă elementul curent (curent) este mai mic decât valoarea tabloului în poziția j (nesortedData (j) ) și dacă este adevărat, atunci sortăm acele valori.
Ierația 1 - curent (96): (96, 542, 42, 1, 6, 37, 21)
Ierație 2 - curent (5): (5, 96, 42, 1, 6, 37, 21)
Ierație 3 - curent (42): (5, 42, 96, 1, 6, 37, 21)
Ierație 4 - curent (1): (1, 542, 96, 6, 37, 21)
Ierație 5 - curent (6): (1, 5, 642, 96, 37, 21)
Ierație 6 - curent (37): (1, 5, 6, 37, 42, 96, 21)
Ierația 7 - curent (21): (1, 5, 6, 21, 37, 42, 96)
Exteriorul pentru iterarea buclelor începe de la prima poziție a indexului, deoarece dorim să mutăm cel mai mic element pe partea stângă, astfel încât comparăm dacă elementul curent este mai mic decât elementele din partea stângă.
Tipuri de sortare
Tipurile de algoritmi folosiți pentru sortarea datelor cuprinde următoarele concepte sau idei în abordarea lor de sortare a datelor:
- Comparație versus strategii bazate pe non-comparație,
- Irativ versus implementarea recursivă,
- Paradigma Împărțiți și-cuceriți (asta sau acela),
- Abordare aleatorie.
Să luăm în considerare câteva exemple:
1. Sortare Merge folosește o abordare divide-și-cucerire pentru a sorta elemente dintr-un tablou.
2. Sortare inserție, Sortare cu bule este un sort bazat pe comparație.
Atunci când datele sunt sortate, devine mai ușor să găsiți o soluție optimă la probleme complexe. de exemplu,
- Căutarea unei anumite valori,
- Găsirea valorii minime sau maxime,
- Testarea unicității și ștergerea duplicatelor,
- Luând în calcul de câte ori a apărut o valoare specifică etc.
Concluzie
În acest articol, am trecut prin definiția sortării de inserție și a complexității sale de timp și a altor tipuri de algoritmi de sortare bazate pe abordarea lor. Studierea diverșilor algoritmi de sortare ne ajută să identificăm care este mai potrivit în anumite circumstanțe sau să utilizăm cazuri care ne ajută să sortăm datele într-un ritm mai rapid.
Articole recomandate
Acesta este un ghid pentru Sortarea inserției în JavaScript. Aici vom discuta despre ce este tipul de inserție în javascript și tipurile sale, cu exemplu. De asemenea, puteți consulta următoarele articole pentru a afla mai multe -
- Modele în JavaScript
- Declarație de caz în JavaScript
- Declarații condiționale în JavaScript
- Obiecte JavaScript
- Diferite tipuri de bucle cu avantajele sale