Confronto dell’algoritmo di ordinamento

Gli algoritmi di ordinamento sono una parte importante della gestione dei dati. AtCprogramming.com, offriamo esercitazioni per capire le tecniche andcommonsorting più importanti. Ogni algoritmo ha particolari punti di forza andweaknesses e in molti casi la cosa migliore da fare è semplicemente utilizzare la funzione di insorting qsort. Per i momenti in cui questa non è un’opzione o hai solo bisogno di un algoritmo di ordinamento rapido e sporco, ci sono una varietà di scelte.

La maggior parte degli algoritmi di ordinamento funziona confrontando i dati ordinati. In somecases, può essere desiderabile ordinare un grande pezzo di dati (per esempio, astruct che contiene un nome e un indirizzo) basato solo su una parte di quei dati.Il pezzo di dati effettivamente utilizzato per determinare l’ordine ordinato è chiamato la chiave.
Gli algoritmi di ordinamento sono solitamente giudicati dalla loro efficienza. In questo caso, l’efficienza si riferisce all’efficienza algoritmica poiché la dimensione dell’input crescegrande e generalmente si basa sul numero di elementi da ordinare. La maggior parte degli algoritmi in uso ha un’efficienza algoritmica di O(n^2) orO(n*log (n)). Alcuni algoritmi di casi speciali(un esempio è menzionato in Programming Pearls) possono ordinare determinati set di dati più velocemente di O(n*log (n)). Thesealgorithms non si basano sul confronto degli elementi ordinati e si basano su tricks. È stato dimostrato che nessun algoritmo di confronto delle chiavi può funzionare megliodi O (n * log (n)).
Molti algoritmi che hanno la stessa efficienza non hanno la stessa velocità sullo stesso input. In primo luogo,gli algoritmi devono essere giudicati in base al loro caso medio, al caso migliore e all’efficienza del caso peggiore. Alcuni algoritmi,come quick sort, funzionano eccezionalmente bene per alcuni input, ma orribilmente per altri. Otheralgorithms, come merge sort, non sono influenzati dall’ordine dei dati di input.Anche una versione modificata di bubble sort può finire in O (n) per gli input più favorevoli.
Un secondo fattore è il “termine costante”. Come big-O notazione astrae via manyof i dettagli di un processo, è abbastanza utile per guardare il bigpicture. Ma una cosa che viene abbandonata è la costante di fronte all’espressione: ad esempio, O(c*n) è solo O(n). Nel mondo reale, theconstant, c, varierà tra diversi algoritmi. Un quicksort ben implementato dovrebbe avere un moltiplicatore costante molto più piccolo rispetto all’heap sort.
Un secondo criterio per giudicare gli algoritmi è il loro requisito di spazio-dothey richiedono spazio zero o l’array può essere ordinato sul posto (senza memoria aggiuntiva oltre alcune variabili)? Alcuni algoritmi non richiedono mai spazio extra, mentre alcuni sono più facilmente comprensibili quando implementati con spazio extra (l’ordinamento dell’heap, ad esempio, può essere eseguito sul posto, ma concettualmente è molto più facile pensare a un heap separato). I requisiti di spazio possono anche dipendere dalla struttura dati utilizzata(ad esempio, unisci ordinamento su array rispetto a unisci ordinamento elenchi collegati).
Un terzo criterio è la stabilità: l’ordinamento conserva l’ordine delle chiavi con valori uguali? La maggior parte dei tipi semplici fa proprio questo, ma alcuni tipi, come heap sort, no.
Il seguente grafico confronta gli algoritmi di ordinamento sui vari criteriaoutlined sopra; gli algoritmi con termini costanti più elevati appaiono per primi, anche se questo è chiaramente un concetto dipendente dall’implementazione e dovrebbe essere preso solo come guida approssimativa quando si sceglie tra i tipi della stessa efficienza big-O.

	Time
Sort	Average	Best	Worst	Space	Stability	Remarks
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	Continuo	Stable	Anche perfettamente ordinati ingresso è necessario eseguire la scansione l’intero array
Insertion Sort	O(n^2)	O(n)	O(n^2)	Continuo	Stable	Nel caso migliore (già ordinati), tutte le operazioni di inserimento richiede una costante di tempo
Heap Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Continuo	Continua	utilizzando l’input array di storage per l’heap, è possibile ottenere la costante di spazio
Merge Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Dipende	Stable	Su array, merge sort richiede spazio O(n); su liste collegate, merge sort richiede un costante spazio
Quicksort	O(n*log(n))	O(n*log(n))	O(n^2)	Continuo	Stable	la selezione Casuale di un valore pivot (o mischiare la matrice prima di ordinare) può aiutare a evitare scenari peggiori come perfettamente array ordinato.