Questo articolo è parte di una serie che copre algoritmi di ordinamento in JavaScript. Puoi trovare il resto della serie qui. Se sei nuovo agli algoritmi di ordinamento, o agli algoritmi in generale, leggi prima questo per ottenere una solida base per andare avanti. Oggi sarò coprendo i pro ei contro di inserimento sorta. L’ordinamento di inserimento è più complesso ma un po ‘ più utile dell’ordinamento a bolle. Lo scenario peggiore per esso è simile a bubble sort, ma il suo caso migliore lo rende adatto per i momenti in cui sei abbastanza sicuro di una lista quasi ordinata o probabilmente già ordinata. Vediamo il quadro generale.
L’ordinamento di inserimento funziona osservando ciascun elemento all’interno di un elenco (iniziando dal secondo elemento) e confrontandolo con l’elemento precedente. Se l’articolo prima è più grande, vengono scambiati. Questo continua fino a quando l’elemento è più piccolo, a quel punto facciamo lo stesso per l’elemento successivo nell’elenco.
L’ordinamento di inserimento non è poi così male.. basta che lo usi nelle giuste circostanze.
- È più veloce della maggior parte degli algoritmi di ordinamento O(n log n) per piccole liste.
- È estremamente efficiente nella memoria che richiede solo O(1) spazio ausiliario per il singolo elemento che viene spostato.
- È stabile: gli elementi uguali appaiono nello stesso ordine nell’elenco ordinato.
- È adattivo: è veloce quando si ordinano elenchi per lo più ordinati o quando si aggiungono elementi a un elenco già ordinato.
- È molto facile da implementare!
Complessità
La complessità temporale di questo algoritmo, nel peggiore dei casi, è quadratica — O(n2). Man mano che n si avvicina all’infinito, il caso medio si avvicina al caso peggiore diviso per due. Tuttavia, poiché se la tua lista è ordinata o quasi, può essere O (n) in uno scenario migliore e quindi ben adattato a quello scenario.
Quando è veloce
Come menzionato sopra può essere veloce in determinate circostanze. Considera l’array, quando usi un algoritmo come merge sort avremmo comunque bisogno di dividere tutti gli elementi e quindi unirli di nuovo. Con l’ordinamento di inserimento abbiamo solo bisogno di verificare che siano nell’ordine corretto “ordinato finora”, quindi spostiamo tutti su un indice per 1.
Poiché l’ordinamento di inserimento è un ordinamento adattivo, lo rende anche un “algoritmo online”, il che significa che possiamo iniziare l’ordinamento prima di ottenere tutti gli elementi e quindi unire gli elenchi una volta completato l’ordinamento parziale.
Pseudocodice
function insertionSort(array)
Loop through array
Create temp var for current element
Create var and set equal to previous element's index
Loop backwards while index >= 0 and current element > temp var
Set next element equal to current element
Set next element equal to temp
Codice
Il prossimo? Unisci ordinamento. Uno degli algoritmi di ordinamento più utilizzati nei browser oggi.
