ももの知恵の樹

C言語アルゴリズム-基数ソート

基数ソート (radix sort)

基数ソートとは、桁数毎に整列することで、全体を整列するアルゴリズムです。基数（radix）というのは、10進数の10、16進数の16というように、桁上がりの基準になる数のことです。１桁目、２桁目、３桁目のように桁ごとにソートしても、順番が保存されていれば整列できるという事を利用するソートです。

ビンソートや分布数え上げソートではデータの範囲が大きくなると整列するために用意するメモリ領域が増大してしまうが、基数ソートならば少量のメモリ領域で安定ソートが実現できます。


基数ソートの整列過程

10進数で、一の位、十の位...とソートしていく場合、以下のように整列されます。 


[整列前]       : 154,  32,  29, 278, 330, 127,  18
[整列：一の位] : 330,  32, 154, 127, 278,  18,  29
[整列：十の位] :  18, 127,  29, 330,  32, 154, 278
[整列：百の位] :  18,  29,  32, 127, 154, 278, 330
[整列後]       :  18,  29,  32, 127, 154, 278, 330

基数ソートの性能

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

データの範囲が広い場合でも、ビンソートのようにメモリを無駄に浪費することがないことが特徴です。

しかし、データの種類が有限で、最大・最小値が明確になっている(データが「3桁の整数」や「2文字のアルファベット」など決まった形式であるなど)ことが条件となります。

限られた状況でのみ圧倒的な速度を出す可能性を秘めていますが、あまり利用できる機会がない整列アルゴリズムといえます。


C言語による基数ソートのプログラム

以下は分布数え上げソートを併用して、4bitずつのシフトして基数ソートする例です。

桁毎の整列で単純にバケットソートを用いるより、分布数え上げソートを利用することが速度の観点からも一般的といえます。 


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

/*!
 * @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');
}

#define DATA_SIZE 12 /* 整列対象のデータ数 */
#define M    16      /* 分布数え上げのキー範囲：０〜１５ */
#define MASK 0x0F    /* 4bitを取り出すためのマスク */

/*!
 * @brief          基数ソートを行う。
 * @param[in/out]  array  整列する要素配列
 * @param[in]      size   配列のサイズ
 */
void
radix_sort(int *array, unsigned int size)
{
    int i, bit; 
    int count[M]; 
    unsigned int buf[DATA_SIZE];

    for(bit = 0; bit < 32; bit += 4){ 
        /* 度数分布を求める */
        for(i = 0; i < M; ++i) count[i] = 0; 
        for(i = 0; i < size; ++i) ++count[(array[i] >> bit) & MASK]; 
        for(i = 1; i < M; ++i) count[i] += count[i-1]; 

        /* 度数分布に従ってデータを整列する */
        for(i = size-1; i>=0; --i){
            buf[--count[(array[i] >> bit) & MASK]] = array[i]; 
        }
        for(i=0; i<size; ++i) array[i] = buf[i]; 
        printf("[%02d bit]:", bit); array_print(array, size);
    } 
}

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

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

    return(0);
}

関連ページ