Lexikografische Sortierung der Wortliste

Question

Ich muss Listen von über 100.000 Wörtern lexikografisch zusammenführen und sortieren. Ich mache es derzeit mit einer leicht modifizierten Blasensortierung, aber bei O (n^2) dauert es eine ganze Weile. Gibt es schnellere Algorithmen zum Sortieren von Wortlisten? Ich benutze Python, aber wenn es eine Sprache gibt, die damit besser umgehen kann, bin ich offen für Vorschläge.

Answer 1

Alle O(nlogn)sorting algorithm tun wird es wahrscheinlich besser, dann Blase Art, aber sie werden O(nlogn * |S|)

jedoch sein, kann das Sortieren Strings in O(n*|S|) geschehen, wo |S| die Länge der durchschnittlichen String, eine trie verwendet, und ein einfach DFS.

High-Level-Pseudocode:

1. create a trie from your collection. 
2. do a DFS on the trie generated, and add each string 
    to the list when you reach terminal node. 

Answer 2

Verwenden Sie die integrierte in sort() Liste Methode:

>>> words = [ 'baloney', 'aardvark' ] 
>>> words.sort() 
>>> print words 
['aardvark', 'baloney'] 

Es verwendet eine O(n lg(n)) Art , die Timsort (.., Die eine merge-Art geändert wird, ich glaube, es ist sehr für die Geschwindigkeit abgestimmt) .

---

Wie bereits in den Kommentaren out, dies auf die Anzahl der Elementvergleiche Bezug nimmt, nicht auf die Anzahl von Low-Level-Operationen. Da die Elemente in diesem Fall Zeichenfolgen sind und der Vergleich von zwei Zeichenfolgen min{|S1|, |S2|} Zeichenvergleiche erfordert, ist die Gesamtkomplexität O(n lg(n) * |S|), wobei |S| die Länge der längsten Zeichenfolge ist, die sortiert wird. Dies gilt jedoch für alle Vergleichssorten. Die tatsächliche Anzahl der Operationen hängt von den Kosten der Elementvergleichsfunktion für die Art der zu sortierenden Elemente ab. Da alle Vergleichsarten die gleiche Vergleichsfunktion verwenden, können Sie diese Feinheit ignorieren, wenn Sie die algorithmische Komplexität dieser Sorten untereinander vergleichen.