Quando viene utilizzato ogni algoritmo di ordinamento?

Quali sono i casi d’uso in cui un particolare algoritmo di ordinamento è preferito rispetto ad altri – merge sort vs quick sort vs heap sort vs intro sort , ecc.?

Esiste una guida consigliata per il loro utilizzo in base alle dimensioni, al tipo di struttura dati, alla memoria e alla cache disponibili e alle prestazioni della CPU?

Innanzitutto, una definizione, poiché è piuttosto importante: un ordinamento stabile è uno che è garantito per non riordinare gli elementi con chiavi identiche.

raccomandazioni:

Ordinamento rapido: quando non è necessario un ordinamento stabile e le prestazioni nel caso medio sono più importanti delle peggiori prestazioni del caso. Un ordinamento rapido è O (N log N) in media, O (N ^ 2) nel caso peggiore. Una buona implementazione utilizza la memoria ausiliaria O (log N) sotto forma di stack space per la ricorsione.

Merge sort: Quando hai bisogno di una stable, O (N log N) sort, questa è la tua unica opzione. L’unico svantaggio è che utilizza lo spazio ausiliario O (N) e ha una costante leggermente più grande di un ordinamento rapido. Esistono alcuni tipi di unione sul posto, ma AFAIK non sono tutti stabili o peggiori di O (N log N). Anche gli ordinamenti di tipo O (N log N) hanno una costante molto più grande del semplice ordinamento di tipo merge che sono più curiosità teoriche che algoritmi utili.

Heap sort: quando non hai bisogno di un ordinamento stabile e ti preoccupi di più delle prestazioni nel caso peggiore rispetto alle prestazioni dei casi medi. È garantito che sia O (N log N) e utilizza lo spazio ausiliario O (1), il che significa che non si esaurirà inaspettatamente spazio heap o stack su input molto grandi.

Introsort: questo è un ordinamento rapido che passa a un ordinamento heap dopo una certa profondità di ricorsione per aggirare il caso peggiore O (N ^ 2) di ordinamento rapido. È quasi sempre meglio di un semplice vecchio ordinamento rapido, poiché si ottiene il caso medio di un ordinamento rapido, con prestazioni O (N log N) garantite. Probabilmente l’unica ragione per usare un ordinamento di heap invece di questo è in sistemi con limitazioni di memoria in cui lo spazio di stack O (log N) è praticamente significativo.

Insertion sort : Quando N è garantito come piccolo, incluso come caso base di un ordinamento rapido o di un tipo di unione. Mentre questo è O (N ^ 2), ha una costante molto piccola ed è un ordinamento stabile.

Bubble sort, sort sort : quando fai qualcosa di veloce e sporco e per qualche motivo non puoi semplicemente usare l’algoritmo di ordinamento della libreria standard. L’unico vantaggio che questi hanno sull’ordinamento per inserimento è leggermente più semplice da implementare.


Tipi non di confronto: in alcune condizioni abbastanza limitate è ansible rompere la barriera O (N log N) e ordinare in O (N). Ecco alcuni casi in cui vale la pena provare:

Tipo di conteggio: quando si selezionano numeri interi con un intervallo limitato.

Ordinamento Radice: quando il registro (N) è significativamente più grande di K, dove K è il numero di cifre radix.

Ordinamento secchio: quando è ansible garantire che il proprio input sia distribuito in modo approssimativamente uniforms.

Una serie di animazioni per diversi tipi di dati e algoritmi può essere trovata su sorting-algorithms.com

Quicksort è in genere il più veloce in media, ma ha alcuni comportamenti peggiori piuttosto brutti. Quindi se devi garantire che nessun dato cattivo ti dia O(N^2) , dovresti evitarlo.

Merge-sort utilizza memoria extra, ma è particolarmente adatto per l’ordinamento esterno (cioè file enormi che non si adattano alla memoria).

Heap-sort può essere ordinato sul posto e non presenta il comportamento quadratico peggiore, ma in media è più lento di quicksort nella maggior parte dei casi.

Nei casi in cui sono coinvolti solo numeri interi in un intervallo limitato, è ansible utilizzare un tipo di ordinamento digitale per renderlo molto veloce.

Nel 99% dei casi, starai bene con i tipi di libreria, che di solito sono basati su quicksort.

La pagina di Wikipedia sugli algoritmi di ordinamento ha una grande tabella di confronto.

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Ciò che i collegamenti forniti ai confronti / animazioni non considerano è quando la quantità di dati supera la memoria disponibile — a quel punto il numero di passaggi sui dati, cioè i costi di I / O, dominano il runtime. Se hai bisogno di farlo, leggi “ordinamento esterno” che di solito copre le varianti degli ordinamenti di unione e heap.

http://corte.si/posts/code/visualisingsorting/index.html e http://corte.si/posts/code/timsort/index.html hanno anche alcune immagini interessanti che confrontano vari algoritmi di ordinamento.

@dsimcha ha scritto: Conteggio ordinamento: quando si selezionano numeri interi con un intervallo limitato

Lo cambierei in:

Ordine di conteggio: quando si ordinano gli interi positivi (0 – Integer.MAX_VALUE-2 a causa della cassetta).

Puoi sempre ottenere i valori massimo e minimo come un’euristica dell’efficienza anche in tempo lineare.
Inoltre è necessario almeno n spazio aggiuntivo per l’array intermedio ed è stabile ovviamente.

 /** * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

(anche se in realtà consentirà di MAX_VALUE-2) vedere: Gli array Java hanno una dimensione massima?

Inoltre vorrei spiegare che la complessità di ordinamento radix è O (wn) per n chiavi che sono numeri interi di word size w. Qualche volta w è presentato come una costante, il che renderebbe l’ordinamento radix migliore (per n sufficientemente grande) rispetto ai migliori algoritmi di ordinamento basati sul confronto, che eseguono tutti i confronti O (n log n) per ordinare le chiavi n. Tuttavia, in generale w non può essere considerato una costante: se tutte le n chiavi sono distinte, allora w deve essere almeno log n per una macchina ad accesso casuale per essere in grado di memorizzarle in memoria, il che dà al meglio una complessità temporale O (n log n). (da wikipedia)