C'è mai una buona ragione per usare Insertion Sort?

Question

Per l'ordinamento generico, la risposta sembra essere negativa, poiché l'ordinamento rapido, l'ordinamento e l'ordinamento dell'heap tendono a ottenere risultati migliori negli scenari medi e pessimi. Tuttavia, l'ordinamento di inserimento sembra eccellere nell'ordinamento incrementale, ovvero aggiungere elementi a un elenco uno alla volta per un lungo periodo di tempo mantenendo l'elenco ordinato, soprattutto se l'ordinamento di inserimento è implementato come un elenco collegato (O (registro n) caso medio vs O (n)). Tuttavia, un heap sembra essere in grado di eseguire solo (o quasi) anche per l'ordinamento incrementale (l'aggiunta o la rimozione di un singolo elemento da un heap ha uno scenario peggiore di O (log n)). Che cosa offre esattamente l'ordinamento di inserzione rispetto ad altri algoritmi o heap di confronto basati su confronto?

Answer 1

Da http://www.sorting-algorithms.com/insertion-sort:

Anche se è uno degli algoritmi di ordinamento elementari con O (n) tempo peggiore, inserzione è l'algoritmo di scelta sia quando i dati sono quasi ordinato (perché è adattivo) o quando la dimensione del problema è piccola (perché ha un sovraccarico ).

Per questi motivi, e perché è anche stabile, inserzione è spesso utilizzato come caso base ricorsivo (quando la dimensione del problema è piccola) per testa divide et impera algoritmi di ordinamento superiori, come unisci l'ordinamento o ordina rapidamente.

Answer 2

La maggior parte delle procedure di ordinamento utilizza quicksort e quindi ordina l'inserimento per set di dati molto piccoli.

Answer 3

Un concetto importante nell'analisi degli algoritmi è asintotica analisi. Nel caso di due algoritmi con diversi tempi di esecuzione asintotici, come uno O (n^2) e uno O (nlogn) come nel caso di insertion sort e quicksort rispettivamente, non è definito che uno sia più veloce dell'altro .

L'importante distinzione con questo tipo di analisi è che per sufficientemente grande N, un algoritmo sarà più veloce di un altro. Quando si analizza un algoritmo con un termine come O (nlogn), si rilasciano le costanti. Quando si analizza realisticamente l'esecuzione di un algoritmo, tali costanti saranno importanti solo per le situazioni di piccolo n.

Che cosa significa? Ciò significa che per alcuni piccoli n, alcuni algoritmi sono più veloci. Questo article di EmbeddedGurus.net include un'interessante prospettiva sulla scelta di diversi algoritmi di ordinamento nel caso di uno spazio limitato (16k) e un sistema di memoria limitato. Ovviamente, l'articolo fa riferimento solo all'ordinamento di un elenco di 20 numeri interi, quindi gli ordini più grandi di n sono irrilevanti. Codice più breve e meno consumo di memoria (oltre a evitare la ricorsione) erano in definitiva decisioni più importanti.

L'ordinamento di inserimento ha un sovraccarico basso, può essere scritto in modo abbastanza sintetico e presenta diversi vantaggi chiave: è stabile e presenta una cassa in esecuzione abbastanza veloce quando l'input è quasi ordinato.

Answer 4

Se stai parlando di mantenere un elenco ordinato, non c'è alcun vantaggio su un qualche tipo di albero, è solo più lento.

Bene, forse consuma meno memoria o è un'implementazione più semplice.

inserimento in un elenco ordinato comporterà una scansione, il che significa che ciascun inserto è O (n), quindi classificare gli n elementi diventa O (n^2)

inserimento in un contenitore come un albero bilanciato, è tipicamente log (n), quindi l'ordinamento è O (n log (n)) che è ovviamente migliore.

Ma per le piccole liste non fa alcuna differenza. Potresti usare un insetto se devi scriverlo da solo senza librerie, le liste sono piccole e/o non ti interessa il rendimento.

Answer 5

SI,

Insertion sort è meglio di rapido Ordina sulle liste brevi.

Infatti, un ordinamento rapido ottimale ha una soglia di dimensione a cui si arresta, quindi l'intero array viene ordinato per tipo di inserimento oltre i limiti di soglia.

anche ...

Per il mantenimento di un quadro di valutazione, Binary inserimento Sort può essere buono come si arriva.

Vedere this page.

Answer 6

Sì, c'è un motivo per utilizzare un tipo di inserzione o una delle sue varianti.

Le alternative di ordinamento (ordinamento rapido, ecc.) Delle altre risposte qui presuppongono che i dati siano già in memoria e pronti per l'uso.

Ma se si sta tentando di leggere una grande quantità di dati da una sorgente esterna più lenta (ad esempio un disco rigido), vi è una grande quantità di tempo sprecato poiché il collo di bottiglia è chiaramente il canale dati o l'unità stessa. Non può stare al passo con la CPU. Una serie naturale di attese si verificano durante ogni lettura. Queste attese sono cicli di CPU sprecati meno che non li usa per sorta, come si va.

Per esempio, se si dovesse fare la vostra soluzione a questo essere la seguente:

1. Leggi una tonnellata di dati in un ciclo dedicato in memoria
2. Ordina che i dati

È molto probabilmente richiederebbe più tempo rispetto a quando si eseguono le seguenti operazioni in due thread.

Discussione A:

1. Leggere un dato
2. Luogo dato in coda FIFO
3. (Ripetere fino dati esausti dal disco)

Discussione B:

1. Ottieni un dato dalla coda FIFO
2. inserirlo nel posto adeguato nella vostra lista ordinata
3. (ripetizione fino coda vuota e filo A dice "done").

... quanto sopra consentirà di utilizzare il tempo altrimenti sprecato. Nota: il thread B non impedisce il progresso del thread A.

Quando i dati vengono letti completamente, saranno ordinati e pronti per l'uso.

Answer 7

Un concetto importante nell'analisi degli algoritmi è l'analisi asintotica. Nel caso di due algoritmi con tempi di esecuzione asintotici diversi, come uno O (n^2) e uno O (nlogn) come nel caso di insertion sort e quicksort rispettivamente, non è definito che uno sia più veloce dell'altro.

L'importante distinzione con questo tipo di analisi è che per N sufficiente, un algoritmo sarà più veloce di un altro. Quando si analizza un algoritmo con un termine come O (nlogn), si rilasciano le costanti. Quando si analizza realisticamente l'esecuzione di un algoritmo, tali costanti saranno importanti solo per le situazioni di piccolo n.

Che cosa significa? Ciò significa che per alcuni piccoli n, alcuni algoritmi sono più veloci. Questo articolo di EmbeddedGurus.net include un'interessante prospettiva sulla scelta di diversi algoritmi di ordinamento nel caso di uno spazio limitato (16k) e un sistema di memoria limitato. Ovviamente, l'articolo fa riferimento solo all'ordinamento di un elenco di 20 numeri interi, quindi gli ordini più grandi di n sono irrilevanti. Codice più breve e meno consumo di memoria (oltre a evitare la ricorsione) erano in definitiva decisioni più importanti.

L'ordinamento di inserimento ha un sovraccarico basso, può essere scritto in modo abbastanza sintetico e presenta diversi vantaggi chiave: è stabile e presenta una cassa in esecuzione abbastanza veloce quando l'input è quasi ordinato.

Answer 8

Per l'allineamento di piccoli array, l'ordinamento è più rapido di Quicksort. Java 7 e Java 8 utilizza quicksort dual pivot per ordinare i tipi di dati primitivi. Quicksort dual pivot esegue il tipico quicksort a pivot singolo. Secondo l'algoritmo di quicksort doppio perno:

1. Per piccoli array (lunghezza < 27), utilizzare l'algoritmo di ordinamento per inserzione.
2. Scegliere due perno ...........

Definetely per inserzione su esegui quicksort per piccoli array ed è per questo che è interruttore inserzione per le matrici di lunghezza inferiore a 27. Il motivo potrebbe essere che non ci sono ricorsi nell'inserimento sort.

Fonte: http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf