L'ordinamento di stringhe per confronto (ad esempio, la funzione standard QuickSort + strcmp) può essere un po 'lento, soprattutto per le stringhe lunghe che condividono un prefisso comune (la funzione di confronto richiede O (s) tempo, dove s è il lunghezza della stringa), quindi una soluzione standard ha la complessità di O (s * nlog n). Esistono algoritmi noti più veloci?Algoritmo di ordinamento stringa efficiente
Se si sa che la stringa contiene solo determinati caratteri (che è quasi sempre il caso), è possibile utilizzare una variante di BucketSort o RadixSort.
Ho fatto una soluzione ibrida per ordinare innanzitutto i suffissi di stringhe usando quicksort e poi il resto usando radixsort. Funziona abbastanza velocemente. Non volevo andare con il puro radix sort visto che alcune stringhe sono lunghe, ma i suffissi sono piuttosto diversi, quindi non è stato male ordinarli usando quicksort. Penso che ci sia ancora spazio per miglioramenti, ma per ora questa soluzione è sufficiente. Grazie –
È possibile creare un trie, che dovrebbe essere O(s*n), credo.
+1, ho sprecato troppo tempo per calcolare la complessità :-) –
@tyz: l'inserimento in un trie dovrebbe essere 'O (s)', e devi farlo 'n' volte. –
Devo pensarci, nella realizzazione diretta sembra un po 'affamato di memoria. –
Si prega di cercare "Sedgewick Multikey quick sort" (Sedgewick ha scritto testi di algoritmi famosi in C e Java). Il suo algoritmo è relativamente facile da implementare e abbastanza veloce. Evita il problema di cui parli sopra. Esiste l'algoritmo di ordinamento a raffica che afferma di essere più veloce, ma non conosco alcuna implementazione.
C'è un articolo Fast String Sort in C# and F# che descrive l'algoritmo e ha un riferimento al codice di Sedgewick e al codice C#. (divulgazione: è un articolo e un codice che ho scritto sulla base del lavoro di Sedgewick).
Sta causando il rallentamento del codice? In caso contrario, non ti preoccupare. – tjameson
Non è la prima volta che incontro questo problema, ma sì, al momento questo ordinamento è una parte, dove il mio programma trascorre molto tempo. –