Introduktion til indsættelse Sorter i JavaScript
Sortering er et af de vigtige begreber, som programmerere lærer at begynde deres rejse inden for datalogi uanset hvilket programmeringssprog der er valgt til at lære. Sortering hjælper os med at finde de måldata, vi vil søge på en hurtigere og bekvem måde, ved at sortere dem i enten stigende eller faldende rækkefølge.
Sorteringsalgoritmer bruges til at omordne elementer, hvor et element kan være et tal eller en streng. Der er mange typer sorteringsalgoritmer baseret på deres sorteringsmetode og den tilgang, de følger for at sortere elementerne, og hver type har sine fordele og ulemper.
I denne blog fokuserer vi på indsættelsessortering, en almindelig sortering, der er let at forstå og implementere.
Hvad er indsættelsessortering i JavaScript?
Indsættelsessortering er en enkel, let at forstå den algoritme, der fungerer bedst med en lille dataliste ved at sortere hvert element i datalisten en efter en fra venstre til højre retning. Det er også kendt som en sammenligningssortering, hvor den sammenligner den aktuelle værdi med de andre værdier i den samme dataliste, der sorteres. Det følger en iterativ tilgang til at placere hvert element i den rigtige rækkefølge på datalisten.
Jo mere tid en algoritme tager at sortere, siges dens ydeevne at være dårlig, og det er nødvendigt at overveje en anden algoritme for at sortere dataene. Indsættelsessortering har en tidskompleksitet på O (n²) eller kører kvadratisk tid for at sortere datalisten i værste tilfælde. Dette er typisk ikke meget effektivt og bør ikke bruges til store lister. Imidlertid er det normalt bedre end avancerede algoritmer, såsom quicksort eller mergesort på mindre lister.
Indsættelsessortering, det meste af tiden er mere effektiv end andre kvadratiske sorteringsalgoritmer, såsom boblesortering eller udvælgelsessortering. Dets bedste case-scenarie, tid er O (n) eller lineær, der opstår, hvis input-arrayet allerede er sorteret. I gennemsnit er indsættelsessorterets køretid stadig kvadratisk.
I nedenstående eksempel har vi en nem tilgang på højt niveau til at sortere data, der er gemt i en array-datastruktur og bruge dens sorteringsmetode til at sortere dataene uden at implementere nogen algoritmer.
Eksempel - indsættelsessorteringsalgoritme
Kode:
// 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));
Produktion:
Forklaring: I algoritmen har vi implementeret 2 for sløjfer, den ydre for loop er at itere over arrayelementerne, og den indre for loop anvendes til at sortere arrayelementerne i stigende rækkefølge af deres værdi. Den aktuelle variabel holder den aktuelle værdi af arrayet, og variablen j er indstillet til en værdi mindre end den aktuelle indeksposition for arrayen. Vi kontrollerer, om det aktuelle element (nuværende) er mindre end array-værdien i j - position (unsortedData (j) ), og hvis det er sandt, sorterer vi disse værdier.
Iteration 1 - strøm (96): (96, 5, 42, 1, 6, 37, 21)
Iteration 2 - strøm (5): (5, 96, 42, 1, 6, 37, 21)
Iteration 3 - strøm (42): (5, 42, 96, 1, 6, 37, 21)
Iteration 4 - strøm (1): (1, 5, 42, 96, 6, 37, 21)
Iteration 5 - strøm (6): (1, 5, 6, 42, 96, 37, 21)
Iteration 6 - strøm (37): (1, 5, 6, 37, 42, 96, 21)
Iteration 7 - strøm (21): (1, 5, 6, 21, 37, 42, 96)
Det ydre til loop-iteration starter ved 1. indeksposition, da vi vil flytte det mindste element til venstre side, så vi sammenligner, om det aktuelle element er mindre end elementerne på venstre side.
Typer af sortering
De typer algoritmer, der bruges til sortering af data, omfatter følgende koncepter eller ideer i deres tilgang til sortering af data:
- Sammenligning versus ikke-sammenligningsbaserede strategier,
- Iterativ versus rekursiv implementering,
- Del-og-erobre paradigme (dette eller det),
- Tilfældig tilgang.
Lad os overveje et par eksempler:
1. Flet sortering bruger en divide-and-conquer-tilgang til at sortere elementer i en matrix.
2. Insertion Sort, Bubble Sort er en sammenligningsbaseret sortering.
Når data sorteres, bliver det lettere at finde en optimal løsning på komplekse problemer. for eksempel,
- Søger efter en bestemt værdi,
- Find minimum eller maksimal værdi,
- Testning for unikhed og sletning af duplikater,
- Tæller hvor mange gange en bestemt værdi er vist osv.
Konklusion
I denne artikel har vi gennemgået definitionen af indsættelsessortering og dens tidskompleksitet og forskellige andre sorteringsalgoritmetyper baseret på deres tilgang. At studere forskellige sorteringsalgoritmer hjælper os med at identificere, hvilken der er bedre egnet under visse omstændigheder eller bruge sager, der hjælper os med at sortere dataene med en hurtigere hastighed.
Anbefalede artikler
Dette er en guide til indsættelsessortering i JavaScript. Her diskuterer vi, hvad der er indsættelsessorter i javascript og dens typer med eksempel. Du kan også se på de følgende artikler for at lære mere -
- Mønstre i JavaScript
- Sagserklæring i JavaScript
- Betingede erklæringer i JavaScript
- JavaScript-objekter
- Forskellige typer loops med dens fordele