Limitazioni delle tecniche di ordinamento basate su confronto

Question

L'ordinamento di confronto viene scelto nella maggior parte degli scenari in cui i dati devono essere ordinati. Tecniche come merge sort, quick sort, insertion sort e altri tipi di confronto possono gestire diversi tipi di dati ed efficienza con un limite inferiore di O (nLog (n)).

Le mie domande sono

1. Ci sono limitazioni di confronto sulla base di smistamento tecniche?
2. Qualsiasi tipo di scenario in cui verrebbero utilizzate tecniche di ordinamento senza confronto?

applausi

Answer 1

avete risposto più o meno da soli. Le tecniche di ordinamento basate sul confronto sono limitate al limite inferiore di O (n Log (n)). Le tecniche di ordinamento senza confronto non soffrono di questo limite. Il problema generale con gli algoritmi di non-ordinamento è che il dominio deve essere più conosciuto e per questo motivo non sono così versatili come le tecniche di confronto.

Pigeonhole sort è un esempio semplice e abbastanza semplice che è abbastanza veloce purché il numero di valori chiave possibili sia vicino al numero di elementi.

Answer 2

Ovviamente le limitazioni dei tipi di confronto sono il fattore tempo - some are better than others, ma se si dispone di un set di dati abbastanza grande, a un certo punto diventeranno tutti troppo lenti. Il trucco è scegliere quello giusto dato il tipo e il mix di dati che stai ordinando.

L'ordinamento senza confronto si basa su altri fattori che ignorano i dati, ad esempio counting sort ordinerà una raccolta di dati, ispezionando ciascun elemento, non confrontandolo con nessun altro valore nella raccolta. L'ordinamento di conteggio è utile per ordinare una raccolta basata su alcuni dati, se tu avessi una raccolta di numeri interi, li ordinerebbe prendendo tutti gli elementi con valore 1 e mettendoli prima nella destinazione, poi tutti gli elementi di valore 2 ecc. (ok, utilizza una matrice "sparsa" per ingrandire rapidamente la raccolta e riordinare i valori, lasciando gli spazi vuoti ma questo è il principio di base)

Answer 3

È facile capire perché il confronto ha bisogno di confronti N log N. Non ci sono! permutazioni e come sappiamo ln (N!) è approssimativamente N ln N - N + O (ln N). Nella notazione O grande, possiamo trascurare termini inferiori a N ln N, e poiché ln e log differiscono solo per costante, otteniamo il risultato finale O (N log N)