Conteggio dell'efficienza dell'algoritmo di ordinamento

Question

Conteggio dell'efficienza dell'algoritmo di ordinamento

#1 da (6 voti)

0

Mentre leggo un libro su "Algorithm Analysis", ho trovato count_sort Algorithm. Tuttavia, ho letto altrove che "Ordinamento / unione veloce" sono gli algoritmi di ordinamento migliori e più efficienti. Ho trovato questo confuso perché la complessità di count_sort è O(n+k) , che è migliore di Mergesort e Quicksort che sono O (n ln n).

La mia domanda:

Qual è il problema con questo Algoritmo di ordinamento?

Quali sono i migliori algoritmi di ordinamento?

def count_sort(seq):
    b, c = [], defaultdict(list)
    for x in seq:
        c[x].append(x)

    for k in range(min(c), max(c)+1):
        b.extend(c[k])
    return b

algorithms sorting

posta user3001937 02.09.2014 - 03:51

fonte

1 risposta

Leggi altre domande sui tag algorithms sorting

Buone pratiche su come fare riferimento a Javascript Come gestisco un server spam che invalida i miei token?

score 6 · Answer 1

Gli ordinamenti di conteggio falliscono quando ci sono grandi valori di chiave (il k nella O (n)). Ciò significa che se hai una grande varietà di valori chiave, il conteggio degli ordinamenti sarà lento. L'ordinamento di Radix può aiutare a risolvere questo problema ma non fa nulla per altri problemi. Entrambi i conteggi e ordinamento digitale sono validi solo per le chiavi intere. Sebbene non sia una limitazione terribilmente seria, vuol dire che il valore di Radix Sort per il numero di cifre in una chiave non dovrebbe essere considerato costante.

C'è anche una piccola questione di complessità spaziale e stabilità nell'ordinamento. Ordinamento Radix richiede un algoritmo di ordinamento stabile da utilizzare come sottotitolo. L'ordinamento di conteggio è stabile, purché si utilizzi una struttura di input e output separata. Se non lo fai, finisci con un tipo instabile. Cioè, potresti finire con elementi nell'ordine sbagliato.

"Best" è un termine molto carico. Non esiste un algoritmo di ordinamento "migliore". Dipenderà da una varietà di fattori tra cui la complessità temporale, la complessità dello spazio, la capacità di parallelizzare l'implementazione e la facilità di implementazione.