Introduzione all'ordinamento per inserzione in JavaScript
L'ordinamento è uno dei concetti importanti che i programmatori imparano per iniziare il loro viaggio nell'informatica indipendentemente dal linguaggio di programmazione selezionato per l'apprendimento. L'ordinamento ci aiuta a individuare i dati di destinazione che vogliamo cercare in modo più rapido e conveniente, ordinandoli in ordine crescente o decrescente.
Gli algoritmi di ordinamento vengono utilizzati per riordinare gli elementi, in cui un elemento può essere un numero o una stringa. Esistono molti tipi di algoritmi di ordinamento basati sul loro metodo di ordinamento e sull'approccio che seguono per ordinare gli elementi, e ogni tipo ha i suoi vantaggi e svantaggi.
In questo blog ci concentreremo sull'ordinamento per inserzione, un ordinamento comune che è facile da capire e implementare.
Che cos'è Insertion Sort in JavaScript?
Insertion Sort è un algoritmo semplice e di facile comprensione che funziona meglio con un piccolo elenco di dati ordinando ogni elemento dell'elenco di dati uno per uno dalla direzione sinistra a destra. È anche noto come ordinamento di confronto in cui confronta il valore corrente con gli altri valori all'interno dello stesso elenco di dati che viene ordinato. Segue un approccio iterativo per posizionare ciascun elemento nel giusto ordine nell'elenco dei dati.
Più tempo impiega un algoritmo per ordinare, le sue prestazioni sono considerate pessime e bisogna considerare un altro algoritmo per ordinare i dati. L'ordinamento per inserzione ha una complessità temporale di O (n²) o esegue un tempo quadratico per ordinare l'elenco di dati nello scenario peggiore. Questo in genere non è molto efficace e non dovrebbe essere usato per elenchi di grandi dimensioni. Tuttavia, di solito supera gli algoritmi avanzati come quicksort o mergesort su elenchi più piccoli.
Ordinamento di inserzione, la maggior parte delle volte è più efficiente di altri algoritmi di ordinamento quadratico come ordinamento a bolle o ordinamento per selezione. Nel migliore dei casi, il tempo è O (n) o lineare, che si verifica se l'array di input è già ordinato. In media, il tempo di esecuzione dell'ordinamento per inserzione è ancora quadratico.
Nell'esempio seguente avremo un semplice approccio di alto livello per ordinare i dati memorizzati in una struttura di dati di array e usare il suo metodo di ordinamento per ordinare i dati senza implementare alcun algoritmo.
Esempio: algoritmo di ordinamento per inserzione
Codice:
// 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));
Produzione:
Spiegazione: Nell'algoritmo, abbiamo implementato 2 per i loop, l'esterno per il ciclo deve iterare sugli elementi dell'array e l'interno per il ciclo viene utilizzato per ordinare gli elementi dell'array in ordine crescente del loro valore. La variabile corrente contiene il valore corrente dell'array e la variabile j è impostata su un valore inferiore alla posizione dell'indice corrente dell'array. Controlliamo se l'elemento corrente (corrente) è più piccolo del valore dell'array in posizione j (unsortedData (j) ) e se è vero, allora ordiniamo quei valori.
Iterazione 1 - corrente (96): (96, 5, 42, 1, 6, 37, 21)
Iterazione 2 - corrente (5): (5, 96, 42, 1, 6, 37, 21)
Iterazione 3 - corrente (42): (5, 42, 96, 1, 6, 37, 21)
Iterazione 4 - corrente (1): (1, 5, 42, 96, 6, 37, 21)
Iterazione 5 - corrente (6): (1, 5, 6, 42, 96, 37, 21)
Iterazione 6 - corrente (37): (1, 5, 6, 37, 42, 96, 21)
Iterazione 7 - corrente (21): (1, 5, 6, 21, 37, 42, 96)
L'iterazione esterna per il ciclo inizia dalla prima posizione dell'indice poiché vogliamo spostare l'elemento più piccolo sul lato sinistro, quindi stiamo confrontando se l'elemento corrente è più piccolo degli elementi sul lato sinistro.
Tipi di ordinamento
I tipi di algoritmi utilizzati per l'ordinamento dei dati comprendono i seguenti concetti o idee nel loro approccio all'ordinamento dei dati:
- Confronto contro strategie non basate sul confronto,
- Implementazione iterativa contro ricorsiva,
- Divide-and-Conquer paradigm (this or that),
- Approccio randomizzato.
Consideriamo alcuni esempi:
1. Unisci ordinamento utilizza un approccio di divisione e conquista per ordinare gli elementi in un array.
2. Ordinamento inserzione, Ordinamento bolla è un ordinamento basato sul confronto.
Quando i dati vengono ordinati, diventa più facile trovare una soluzione ottimale a problemi complessi. per esempio,
- Alla ricerca di un valore specifico,
- Trovare il valore minimo o massimo,
- Verifica dell'unicità ed eliminazione dei duplicati,
- Contando quante volte è apparso un valore specifico, ecc.
Conclusione
In questo articolo, abbiamo esaminato la definizione dell'ordinamento per inserzione e la sua complessità temporale e vari altri tipi di algoritmo di ordinamento in base al loro approccio. Lo studio di vari algoritmi di ordinamento ci aiuta a identificare quale è più adatto in determinate circostanze o utilizzare casi che ci aiutano a ordinare i dati a una velocità maggiore.
Articoli consigliati
Questa è una guida all'ordinamento per inserzione in JavaScript. Qui discutiamo dell'esempio dell'inserimento in javascript e dei suoi tipi. Puoi anche consultare i seguenti articoli per saperne di più -
- Pattern in JavaScript
- Dichiarazione del caso in JavaScript
- Dichiarazioni condizionali in JavaScript
- Oggetti JavaScript
- Diversi tipi di loop con i suoi vantaggi