La clasificación de cadenas por comparación (ej. Estándar QuickSort + función strcmp) puede ser un poco lenta, especialmente para cadenas largas que comparten un prefijo común (la función de comparación toma O (s) tiempo, donde s es el longitud de la cadena), por lo tanto, una solución estándar tiene la complejidad de O (s * nlog n). ¿Hay algún algoritmo conocido más rápido?Algoritmo eficiente de clasificación de cadenas
Si sabe que la cadena consta solo de ciertos caracteres (que casi siempre es el caso), puede usar una variante de BucketSort o RadixSort.
Hice una solución híbrida para primero ordenar los sufijos de cadenas usando quicksort y luego el resto usando radixsort. Funciona bastante rápido. No quería ir con la clasificación de radix puro, ya que algunas cadenas son largas, pero los sufijos son bastante diferentes, por lo que no me costó clasificarlos usando la orden rápida. Creo que todavía hay margen de mejora, pero por ahora esta solución es suficiente. Gracias –
Puede construir un trie, que debería ser O(s*n), creo.
+1, perdí demasiado tiempo para calcular la complejidad :-) –
@tyz: La inserción en un trie debe ser 'O (s)', y debe hacerlo 'n' veces. –
Tengo que pensarlo, en la implementación directa parece estar un poco hambriento de memoria. –
Busque "Sedgewick Multikey quick sort" (Sedgewick escribió famosos libros de texto de algoritmos en C y Java). Su algoritmo es relativamente fácil de implementar y bastante rápido. Evita el problema al que te refieres arriba. Existe el algoritmo de clasificación de ráfaga que dice ser más rápido, pero no conozco ninguna implementación.
Hay un artículo Fast String Sort in C# and F# que describe el algoritmo y tiene una referencia al código de Sedgewick así como al código C#. (divulgación: es un artículo y código que escribí basado en el artículo de Sedgewick).
¿Está causando que su código sea lento? Si no, no te preocupes por eso. – tjameson
No es la primera vez que encuentro este problema, pero sí, en el momento en que esta clasificación es una parte, donde mi programa pasa mucho tiempo. –