C言語アルゴリズム-分布数え上げソート

分布数え上げソート（distribution counting sort）

分布数え上げソートとは、データをキーにして、キーの出現回数とその累積度数分布を計算して利用することで整列を行うアルゴリズムです。

キーが重複した場合にも安定な整列が可能なアルゴリズムです。

分布数え上げソートの整列過程

「5, 2, 0, 4, 4, 5, 3」というデータ列があった場合、値をキーと見なして出現頻度を調べることで、以下のキー分布を知ることができます。

キー	出現数	累計度数分布
0	1	1
1	0	1
2	1	2
3	1	3
4	2	5
5	2	7

データ列末尾の「3」は累計度数分布で「3」なので、「配列の3番目（添字は2）」に格納します。そして、データ列の「3」を取り出したことで、累計度数分布は「2」に減らします。

次に、データ列末尾の「5」は累計度数分布で「7」なので、「配列の7番目（添字は6）」に格納します。そして、データ列の「5」を取り出したことで、累計度数分布は「6」に減らします。

このような手順で、データ列の後ろから全てのデータを配列に格納していくことで整列することができます。なお、データ列の後方から格納することは安定化ソートの役割となります。


[整列前]    :5 2 0 4 4 5 3 
[度数分布]  :1 1 2 3 5 7 7 
--------------[整列処理]--------------
data=3 --> array[2]
[度数分布]  :1 1 2 2 5 7 7 
data=5 --> array[6]
[度数分布]  :1 1 2 2 5 6 7 
data=4 --> array[4]
[度数分布]  :1 1 2 2 4 6 7 
data=4 --> array[3]
[度数分布]  :1 1 2 2 3 6 7 
data=0 --> array[0]
[度数分布]  :0 1 2 2 3 6 7 
data=2 --> array[1]
[度数分布]  :0 1 1 2 3 6 7 
data=5 --> array[5]
[度数分布]  :0 1 1 2 3 5 7 
------------------------------------
[整列後]    :0 2 3 4 4 5 5

分布数え上げソートの問題点

キーとなるデータがとりうる値の範囲をあらかじめ知っている必要がありま。（ビンソートと同じです。）

分布数え上げソートの性能

計算量は「O(n)」であり、値を比較するようなソートでは不可能な処理速度を実現することができます。

ただし、最低でも合計２回の走査（要素の数を数えるための走査と、実際にソートをするための走査）が必要になるため、ソートしようとしているデータの規模によっては低速となります。

C言語による分布数え上げソートのプログラム


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 12

/*!
 * @brief       配列にランダムな数値を格納する。
 * @param[out]  array  数値格納先の配列
 * @param[in]   size   配列のサイズ
 * @param[in]   digit  数値の桁数。
 */
static void
array_random_number(int *array, unsigned int size, unsigned int digit)
{
    int i;

    /* 起動毎に異なる乱数を発生させる */
    srand((unsigned int)time(NULL));
    for(i = 0; i < size; i++){
        array[i]=rand() % digit;
    }
}

/*!
 * @brief       配列内容を表示する
 * @param[in]   array  数値格納先の配列
 * @param[in]   size   配列のサイズ
 */
static void
array_print(int *array, unsigned int size)
{
    int i = 0;

    for(i = 0; i < size; i++){
        printf("%d ", array[i] );
    }
    putchar('\n');
}

/*!
 * @brief       度数分布を求める
 * @param[in]   data_array  整列する要素配列
 * @param[in]   array_size  配列のサイズ
 * @param[out]  dist_table  度数分布の配列
 * @param[in]   dist_size   配列のサイズ
 */
static void
create_dist_table(int *data_array, unsigned int array_size,
                  int *dist_table, unsigned int dist_size)
{
    int cnt = 0;

    /* 分布カウンタを初期化する */
    for(cnt = 0; cnt < dist_size; cnt++){
        dist_table[cnt] = 0;
    }

    /* キーを数え上げる */
    for(cnt = 0; cnt < array_size; cnt++){
        dist_table[data_array[cnt]]++;
    }

    /* キーの累積度数分布を求める */
    for(cnt = 0; cnt < dist_size; cnt++){
        dist_table[cnt + 1] += dist_table[cnt];
    }
}

/*!
 * @brief          分布数え上げソートを行う。
 * @param[in/out]  array  整列する要素配列
 * @param[in]      size   配列のサイズ
 * @note           安定化のために後ろから整列します。
 * @todo           変数idx,dataは理解しやすくするためなので消すこと。
 */
void
distribution_count_sort(int *array, unsigned int size)
{
    int dist_table[DATA_SIZE]; /* 累計度数分布用のテーブル */
    int buf[DATA_SIZE];        /* 一時保存用の配列 */
    int cnt = 0;
    int idx = 0;
    int data = 0;

    /* 度数分布を求める */
    create_dist_table(array, size, dist_table, sizeof(dist_table)/4);
    printf("[dist]  :"); array_print(dist_table, sizeof(dist_table)/4);

    /* 整列する */
    for(cnt = size - 1; cnt >= 0; cnt--){
        data = array[cnt];           /* 配列末尾のデータを取り出す */
        idx  = dist_table[data] - 1; /* 累計値から格納先の添字を知る */
        buf[idx] = data;             /* データを配列に格納する */
        dist_table[data]--;          /* 度数分布の値を減算する */

        /* DEBUG:度数分布の変化を表示する */
        printf("data=%d --> array[%d]\n", data, idx);
        printf("[dist]  :"); array_print(dist_table, sizeof(dist_table)/4);
    }

    /* 整列データを格納しなおす */
    for(cnt = 0; cnt < size; cnt++){
        array[cnt] = buf[cnt];
    }
}

int
main(void)
{
    int data[DATA_SIZE];
    array_random_number(data, sizeof(data)/4, DATA_SIZE);

    printf("[before]:"); array_print(data, sizeof(data)/4);

    distribution_count_sort(data, sizeof(data)/4);

    printf("[after] :"); array_print(data, sizeof(data)/4);

    return(0);
}

関連ページ