Sortierung Array-Elemente auf der Grundlage der Häufigkeit von jedem Element

Question

Ich bin auf der Suche nach einem Algorithmus in C, Array-Elemente nach Häufigkeit sortiert (am wenigsten zu am häufigsten). Zum Beispiel:

array[10] = {1, 1, 1, 5, 2, 3, 3, 3, 3, 4}; //initial array 

array[10] = {5, 4, 2, 1, 1, 1, 3, 3, 3, 3}; //post-sorting array 

Die Reihenfolge der Elemente mit ähnlichen Frequenzen (5, 4 und 2 in dem obigen Beispiel) keine Rolle, solange sie mit anderen der gleichen Frequenz gruppiert sind.

Ich bin nicht sicher, wie man das macht, sah ich THIS, aber es ist in Matlab (die ich nicht weiß), anstatt C, und es beruht stark auf Bibliotheksfunktionen, etwas, das ich nicht versuche machen.

Answer 1

typedef eine Struktur mit Wert und Häufigkeit. Erstellen Sie ein Array von 10 davon, um eine Häufigkeitstabelle zu erstellen, und legen Sie zunächst eine Tabellenanzahl auf 0 fest.

Iterieren Sie das Quell-Array und fügen Sie die Häufigkeitstabelle zusammen, indem Sie den Zähler zählen, wenn ein Wert gefunden wird, der noch keinen Tabelleneintrag enthält.

Verwenden Sie qsort, um die Häufigkeitstabelle nach aufsteigender Häufigkeit zu sortieren.

Iterieren Sie die sortierte Häufigkeitstabelle, erstellen Sie Array und geben Sie Array aus, wie Sie gehen. Sie könnten das Eingabearray als Ausgabearray verwenden, wenn Sie möchten.

Wenn Sie die Funktion qsort lib nicht verwenden möchten, ersetzen Sie Ihre eigene Sortierung.

Answer 2

Sie könnten eine Struktur erstellen, die das Element und die Häufigkeit des Elements enthält, und Sie könnten auch Duplikate vermeiden, wenn Sie ein Element in das Array einfügen, indem Sie einfach das Häufigkeitsfeld vergrößern.

Zum Beispiel:

typedef struct elem{ 
    int value; 
    int freq; 
} element; 

und dann sortieren Sie die Array element[N] frequenzweise, vielleicht mit einem Algorithmus wie qsort