Effizientester Sortieralgorithmus für eine große Menge von Zahlen

Question

Ich arbeite an einem großen Projekt, ich werde mir nicht die Mühe machen, es hier zusammenzufassen, aber dieser Teil des Projekts ist es, ein sehr großes Dokument von Text (mindestens rund 50.000 Wörter (nicht eindeutig)) zu nehmen, und jedes einzelne Wort in der Reihenfolge der am häufigsten verwendeten zu am wenigsten verwendet (wahrscheinlich Top drei werden "ein" "an" und "die").

Meine Frage ist natürlich, was wäre der beste Sortieralgorithmus zu verwenden? Ich las von Zählen sortieren, und ich mag es, aber meine Sorge ist, dass der Bereich der Werte zu groß im Vergleich zu der Anzahl der eindeutigen Wörter sein wird.

Irgendwelche Vorschläge?

Answer 1

In fast allen Fällen, die ich jemals getestet habe, hat Quicksort am besten funktioniert. Allerdings hatte ich zwei Fälle, in denen Combsort am besten funktionierte. Könnte sein, dass Combsort in diesen Fällen besser war, weil der Code so klein war, oder aufgrund einer Eigenart, wie die Daten geordnet waren.

Jedes Mal, wenn in meinem Profil eine Sortierung auftaucht, versuche ich es mit den Hauptsortierungen. Ich hatte noch nie etwas, das Quicksort und Combsort übertraf.

Answer 2

Ich denke, Sie möchten etwas tun, was im folgenden Beitrag beschrieben wird:

http://karephul.blogspot.com/2008/12/groovy-closures.html

Sprachen, die Closure unterstützen, machen die Lösung viel einfacher, wie z.B. LINQ, wie Eric erwähnt hat.

Answer 3

Für große Mengen können Sie die so genannte "sortierungsbasierte Indizierung" verwenden, aber für 50.000 Wörter können Sie Folgendes verwenden:

• die gesamte Datei in einen Puffer einlesen.
• den Puffer parsen und einen Token-Vektor mit struct token { char *term, int termlen; } term ist ein Zeiger auf das Wort im Puffer.
• sortiert die Tabelle nach Begriffen (lexikografische Reihenfolge).
• set entrynum = 0, iteriert durch den Termvektor, wenn der Begriff neu ist, speichere ihn in einem Vektor: struct { char *term; int frequency; } bei Index entrynum, Frequenz auf 1 setzen und die Eintragsnummer inkrementieren, sonst Frequenz inkrementieren.
• sortiert den Vektor nach Häufigkeit in absteigender Reihenfolge.

Answer 4

Sie können auch versuchen, digitale Bäume, auch bekannt als Trie, zu implementieren. Hier ist die Link