Quali sono in pratica gli algoritmi di ordinamento più popolari? [chiuso]

1

Anche se sospetto che la risposta a questa domanda possa essere qualcosa del tipo "la popolarità è irrilevante, ogni algoritmo ha i suoi compromessi", sono interessato a un elenco di algoritmi di ordinamento popolari usati nella pratica.

Stavo sfogliando la pagina di Wikipedia sugli algoritmi di ordinamento e mentre non ci sono molti algoritmi elencati qui, continuo a non farlo Li vediamo tutti usati. Ad esempio, sicuramente l'ordinamento di selezione non verrebbe utilizzato nella pratica poiché ha un O(n^2) giusto? Quindi, che sono utilizzati in pratica molto?

    
posta Jason 07.03.2013 - 00:38
fonte

3 risposte

6

Innanzitutto, leggi Quali sono i criteri per la scelta di un algoritmo di ordinamento? Ti aspetteremo.

Hai finito di leggere? OK. Per rispondere alla tua domanda, Microsoft ha scelto un " unstable "algoritmo stabile per il loro metodo Array.Sort() . Immagino sia una buona idea di un algoritmo di ordinamento come qualsiasi altro.

    
risposta data 07.03.2013 - 00:49
fonte
4

Prima di tutto nota che l'ordinamento è il problema più studiato in CS. E per una buona ragione. A un certo punto la maggior parte del tempo del computer è andato in cernita. Probabilmente le ricerche di hash superano quelle odierne, ma mi aspetto che l'ordinamento sia ancora nei primi 2 utilizzi produttivi del tempo di CPU. (Se hai a che fare con big data set, è quasi certamente il numero # 1.)

Quindi ci sono molti algoritmi di ordinamento e le persone hanno studiato esattamente quando ognuno è il migliore. È stato analizzato pesantemente tutto ciò che si può pensare dal costo di una errata previsione delle filiali alla velocità di accesso a diversi tipi di archiviazione dei dati. Le persone hanno provato un sacco di cose e hanno trovato ruoli utili per loro. Sì, anche selezione sort.

Per le piccole liste, quicksort è stato a lungo il preferito. In questi giorni Timsort sta guadagnando popolarità (usato di default in Python e Java). Sono stati usati molti, molti altri algoritmi di ordinamento e, in generale, qualunque sia l'impostazione predefinita nella tua lingua non si rivelerà un collo di bottiglia.

Per i set di dati di grandi dimensioni, il chiaro vincitore è l'unisci sort. La sua capacità di trasmettere dati (che funziona bene con dischi di grandi dimensioni), la facilità di parallelizzazione e la mancanza di hot spot gli danno una grande spinta. Naturalmente ci sono molti dettagli che devi capire. E così ci sono molti diversi tipi specifici che vengono utilizzati, ma sotto il cofano quelli buoni sono schiaccianti basati sull'unione sort.

Vedi link per un'immagine di ciò che è possibile nella fascia alta e le descrizioni di come lo fanno.

Ogni serio linguaggio di programmazione ha incorporato algoritmi di ordinamento. Per le piccole liste dovresti semplicemente usarlo e starai bene. Se i tuoi dati sono più grandi, usa l'utilità di ordinamento Unix (che, per i dati di grandi dimensioni, sarà un ordinamento di fusione sotto il cofano). Se i tuoi dati sono così grandi da dover essere parallelizzati, dovresti trovare qualcosa di pre-costruito per il tuo caso d'uso. (I framework MapReduce usano sort internamente, quindi Hadoop è spesso "abbastanza buono".) Se alcuni altri usi non sono soddisfatti da questi tre casi d'uso, la mia esperienza dice che probabilmente applicherete qualche variazione su un ordinamento di tipo merge.

    
risposta data 07.03.2013 - 01:38
fonte
3

L'implementazione di ordinamento predefinita tipica per la maggior parte delle lingue che ho utilizzato è Mergesort o Quicksort. Python e sempre più altre lingue usano Timsort che è un Mergesort che cerca blocchi precompilati per accelerare l'ordinamento. Solitamente Mergesort verrebbe selezionato se il tuo caso peggiore fosse importante ma il tuo spazio non lo fosse e Quicksort se il contrario è vero.

Vedrai solo un sottoinsieme piuttosto piccolo non solo per la complessità del tempo e dello spazio, ma anche perché la parallelizzazione favorisce gli algoritmi che dividono e conquistano ciò che fanno ricorso a Mergesort e Quicksort.

La parallelizzazione apre nuovi tipi come il Sortion Bitonic che opera nel log ^ 2 (n) tempo però nello spazio è nlog ^ 2 (n).

    
risposta data 07.03.2013 - 01:03
fonte

Leggi altre domande sui tag