Was sind effiziente Möglichkeiten, um Arrays zu sortieren, die meist nur einen kleinen Satz duplizierter Elemente enthalten? Das ist eine Liste wie:
{10, 10, 55, 10, 999, 8851243, 10, 55, 55, 55, 10, 999, 8851243, 10}
Unter der Annahme, dass die Reihenfolge der equal -Elemente keine Rolle spielt, was sind gute Worst-Case- / Durchschnitts-Algorithmen?
In der Praxis können Sie zuerst einmal durch das Array iterieren und eine Hash-Tabelle verwenden, die die Anzahl der Vorkommen der einzelnen Elemente zählt (dies ist O (n), wobei n = Größe der Liste). Dann nimm alle eindeutigen Elemente und sortiere sie (das ist O (k log k) mit k = Anzahl der eindeutigen Elemente), und dehne dann dieses zurück zu einer Liste von n Elementen in O (n) Schritten und erhole die Zählungen von Hash-tabelle. Wenn k & lt; & lt; n Sie sparen Zeit.
Nicht der beste Algorithmus, aber einfach:
Du kannst alles in einen Trie setzen und die Blätter als Zähler haben. Das sollte O (n * m) annehmen, wobei n die Anzahl der Elemente und m die Größe des größten Elements ist (typischerweise wäre das eine Konstante, aber nicht notwendigerweise). Dann vorbestellen Sie die Krawatte und geben counter Elemente des aktuellen Schlüssels aus, wenn Sie ein Blatt treffen. Das sollte nur O (n + p) nehmen, wobei p die Größe des Trie ist, was im Vergleich zu n winzig sein sollte.
Ich würde Counting sort mit einer Mapping-Funktion versuchen. Ie. Sie werden nicht das Array der Frequenzen verwenden, dessen Größe dem Bereich der Elemente entspricht, stattdessen würden Sie über das Array iterieren, verschiedene Elemente aufschreiben und sie in einer Mapping-Funktion für das Array von Frequenzen verwenden.
Auf diese Weise hat der Algorithmus nur eine zusätzliche Iteration und eine Mapping-Funktion, die in einer konstanten Zeit funktionieren sollte (unter Verwendung einer King of Hash-Tabelle). Die Komplexität dieses Ansatzes wäre O(n) , was optimal sein sollte.
Implementierung in C ++ basierend auf Algo wie von @Antti Huima vorgeschlagen
überschreibt Input-Array mit sortierten Elementen in Abhängigkeit von den Frequenzen.
%Vor%IMO Pidgeonhole-Sortierung ist ein gutes Beispiel für solche Daten.
Ich werde ein wenig klarstellen: Wenn Sie wissen, dass die Menge der einzigartigen Elemente im Array vernünftig ist und Sie wissen, dass es viele Duplikate gibt, würde ich mir vorstellen, sowas wie das Zählen von Sortierung zu implementieren, aber die Liste der "Buckets" dynamisch zu machen . Nach dem ersten Durchlauf werden Sie die Duplikate los, sortieren Sie dann das Array ohne Duplikate mit einem guten Sortieralgorithmus und stellen Sie das sortierte Array wieder her, ähnlich wie das Zählen von Sort.
Tags und Links algorithm language-agnostic performance sorting duplicates