Introduktion till Insertion Sortera i JavaScript
Sortering är ett av de viktiga begreppen som programmerare lär sig att börja sin resa inom datavetenskap oavsett vilket programmeringsspråk som valts att lära sig. Sortering hjälper oss att hitta måldata som vi vill söka på ett snabbare och bekvämt sätt genom att sortera dem i antingen stigande eller fallande ordning.
Sorteringsalgoritmer används för att ordna om element, där ett element kan vara ett nummer eller en sträng. Det finns många typer av sorteringsalgoritmer baserade på deras sorteringsmetod och den metod de följer för att sortera elementen, och varje typ har sina fördelar och nackdelar.
I den här bloggen kommer vi att fokusera på insättningssortering, en vanlig sortering som är lätt att förstå och implementera.
Vad är Insertion Sort i JavaScript?
Insertion Sort är en enkel, lätt att förstå den algoritm som fungerar bäst med en liten datalista genom att sortera varje element i datalistan en efter en från vänster till höger riktning. Det är också känt som en jämförelsesort där den jämför det aktuella värdet med de andra värdena i samma datalista som sorteras. Det följer en iterativ strategi för att placera varje element i rätt ordning i datalistan.
Ju mer tid en algoritm tar att sortera sägs dess prestanda vara dålig och måste överväga en annan algoritm för att sortera upp data. Insättningssortering har en tidskomplexitet på O (n²) eller kör kvadratisk tid för att sortera datalistan i värsta fall. Detta är vanligtvis inte särskilt effektivt och bör inte användas för stora listor. Men det överträffar vanligtvis avancerade algoritmer som kvicksort eller sammansortering på mindre listor.
Insättningssortering är för det mesta effektivare än andra kvadratiska sorteringsalgoritmer som bubbelsortering eller urvalssortering. Det bästa fallet, tiden är O (n) eller linjär, vilket inträffar om inmatningsfältet redan är sorterat. I genomsnitt är insättningssortens körtid fortfarande kvadratisk.
I exemplet nedan kommer vi att ha en enkel strategi på hög nivå för att sortera data lagrade i en matrisdatastruktur och använda dess sorteringsmetod för att sortera data utan att implementera några algoritmer.
Exempel - Insertion Sort Algoritm
Koda:
// 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:
Förklaring: I algoritmen har vi implementerat 2 för slingor, den yttre för slingan är att iterera över arrayelementen och den inre för slingan används för att sortera arrayelementen i stigande ordning på deras värde. Den aktuella variabeln håller det aktuella värdet på arrayen och variabeln j är inställd på ett värde mindre än den aktuella indexpositionen för arrayen. Vi kontrollerar om det aktuella elementet (nuvarande) är mindre än matrisvärdet i j: e position (unsortedData (j) ) och om det är sant så sorterar vi dessa värden.
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 - nuvarande (21): (1, 5, 6, 21, 37, 42, 96)
Det yttre för loop-iteration börjar vid 1: a indexläget eftersom vi vill flytta det minsta elementet till vänster så att vi jämför om det aktuella elementet är mindre än elementen på dess vänstra sida.
Typer av sortering
De typer av algoritmer som används för att sortera data omfattar följande begrepp eller idéer i deras sätt att sortera data:
- Jämförelse jämfört med icke-jämförelsebaserade strategier,
- Iterativ kontra rekursiv implementering,
- Divide-and-Conquer-paradigmet (detta eller det),
- Slumpmässigt tillvägagångssätt.
Låt oss överväga några exempel:
1. Sortera sortering använder en uppdelning och erövreringsmetod för att sortera element i en matris.
2. Insertion Sort, Bubble Sort är en jämförelsebaserad sortering.
När data sorteras blir det lättare att hitta en optimal lösning på komplexa problem. till exempel,
- Söker efter ett specifikt värde,
- Hitta minsta eller högsta värde,
- Testa för unikhet och radera duplikat,
- Räknar hur många gånger ett specifikt värde har dykt upp, etc.
Slutsats
I den här artikeln har vi gått igenom definitionen av insättningssortering och dess tidskomplexitet och olika andra sorteringsalgoritmtyper baserat på deras tillvägagångssätt. Att studera olika sorteringsalgoritmer hjälper oss att identifiera vilken som är bäst lämpad vid vissa omständigheter eller använda fall som hjälper oss att sortera informationen i en snabbare takt.
Rekommenderade artiklar
Detta är en guide till Insertion Sort in JavaScript. Här diskuterar vi vad som är insättningssortering i javascript och dess typer med exempel. Du kan också titta på följande artiklar för att lära dig mer -
- Mönster i JavaScript
- Ärendena i JavaScript
- Villkorliga uttalanden i JavaScript
- JavaScript-objekt
- Olika typer av slingor med dess fördelar