Während ich an einem Beispielcode für eine Algorithmusfrage arbeitete, stieß ich auf die Situation, in der ich ein Eingabearray sortierte, obwohl ich nur identische Elemente gruppieren musste, aber nicht in einer bestimmten Reihenfolge,

{1,2,4,1,4,3,2} → {1,1,2,2,4,4,3} oder {1,1,2,2,3,4,4} oder { 3,1,1,2,2,4,4} oder ...

Was hat mich gewundert: Ist es möglich, identische Elemente in einem Array effizienter zu gruppieren als durch Sortieren des Arrays?

Einerseits bedeutet die Tatsache, dass Elemente nicht an einen bestimmten Ort verschoben werden müssen, mehr Freiheit, um einen Auftrag zu finden, der weniger Auslagerungen erfordert. Auf der anderen Seite müssen Sie möglicherweise mehr Berechnungen durchführen, um festzustellen, wo sich jedes Element in einer Gruppe befindet und wie die optimale endgültige Position lautet, als nur das Array zu sortieren.

Ein logischer Kandidat wäre eine Art voncounting sort, aber was ist, wenn die Arraylänge und / oder der Wertebereich unpraktisch groß sind?

Aus Gründen des Arguments nehmen wir an, das Array ist groß (z. B. eine Million Elemente), enthält 32-Bit-Ganzzahlen und die Anzahl identischer Elemente pro Wert kann zwischen 1 und 1 Million liegen.

UPDATE: Für Sprachen mit Unterstützung für Wörterbücher ist Salvador Dalis Antwort offensichtlich der richtige Weg. Ich wäre immer noch daran interessiert, etwas über altmodische Compare-and-Swap-Methoden zu erfahren oder über Methoden, die weniger Speicherplatz beanspruchen, falls vorhanden.