【C言語】配列の要素を出現回数つきで降順に表示する方法

int型の要素を持つ配列が与えられたとき、各要素を降順に並べて表示し、同時にそれぞれの出現回数（頻度）を求めるのがこの記事の目的です。

ここでは、あらかじめ昇順にソートされた配列を後ろから走査することで、効率よく値ごとの出現回数をカウントしていく手法を紹介します。

入力と出力の例

入力 : arr[]={1,1,1,2,2,2,3,3,4,5,6,7,7}
出力 : 7 occurs: 2
   6 occurs: 1
   5 occurs: 1
   4 occurs: 1
   3 occurs: 2
   2 occurs: 3
   1 occurs: 3

この例では、最大値の「7」から最小値の「1」へ向かって各数値が表示され、その横に何回出現したかが出力されています。

アルゴリズム

処理の流れは以下の通りです。

START
Step 1 -> 昇順にソートされた要素を持つ配列を用意する
Step 2 -> sizeof(a)/sizeof(a[0]) で配列のサイズを計算する
Step 3 -> サイズを変数 en に格納する
Step 4 -> i=siz-1 から i>0 の間ループを回す
  IF a[i]!=a[i-1] ならば
    to = en-i を設定
    a[i] と to を出力
    en = i を設定
  End
Step 5 -> a[0] と to を出力
STOP

ポイントは、隣り合う要素が異なるタイミングで「そこまでの区間の長さ」が出現回数になるという性質を利用している点です。ソート済み配列では同じ値が連続して並ぶため、境界位置の差分を取るだけで頻度を求められます。

サンプルコード

#include<stdio.h>
int main() {
   int a[]={1,1,1,2,2,2,3,3,4,5,6,7,7};
   int siz,i,en,st,to;
   siz=sizeof(a)/sizeof(a[0]);
   en=siz;
   for(i=siz-1;i>0;i--) {
      if(a[i]!=a[i-1]) {
         to=en-i;
         printf("%d occurs: %d\n",a[i],to);
         en=i;
      }
   }
   to=en;
   printf("%d occurs: %d\n",a[0],to);
}

コードの解説

• siz: sizeof演算子を使い、配列全体のバイト数を要素1個分のバイト数で割ることで要素数を求めています。
• en: 次に異なる値が見つかったときの基準位置を保持する変数です。
• to: 前回の境界位置との差分、すなわち現在の値の出現回数を表します。
• ループ終了後に残る a[0]（最小値）の出現回数も忘れずに出力しています。

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

7 occurs: 2
6 occurs: 1
5 occurs: 1
4 occurs: 1
3 occurs: 2
2 occurs: 3
1 occurs: 3

このように、ソート済み配列を一度だけ走査すればよいため、計算量は O(n) と非常に効率的です。頻度集計やヒストグラム作成など、さまざまな場面で応用できるテクニックなので、ぜひ覚えておきましょう。