ももの知恵の樹

C言語アルゴリズム-ビンソート

ビンソート (bin sort)

ビンソートとは、データの取りうる値に対応した格納領域を事前に用意しておき、データを適切な位置へ挿入していくことで整列を行うアルゴリズムです。例えば０～１００の値をソートする場合、１０１個の配列を用意しておき、データを添字に対応する箇所に格納します。この配列を先頭から取り出すと整列されたデータ列を取得することができます。なお、ビンソートのビンとは、ゴミなどを入れておく大きな容器のことです。また、容器をバケツとみなして「バケットソート」とも呼ばれることもあります。

ビンソートは、比較によらない整列アルゴリズムです。


ビンソートの整列過程

例として、データ列「4 1 7 3 5」を整列します。


（手順１）　データ自体の値を添字にして配列に格納します。

添字 0 1 2 3 4 5 6 7
データ - 1 - 3 4 5 - 7

（手順２）　配列から昇順にデータを取得すれば「1 3 4 5 7」という昇順の整列データを取得できます。


ビンソートの性能

ビンソートでは、どれだけデータが増えても「ビンに格納する」という操作回数が単に増えていくだけなので、性能が落ちにくい利点があります。

クイックソートではデータ量が千倍になれば処理速度は約１万倍遅くなりますが、バケットソートではデータ量が千倍になっても処理速度は千倍になります。

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


ビンソートの問題点

ビンソートを実現するためには、いくつかの問題点があります。

  • 整数の配列で、要素の値の取る範囲が予め判明している時にしか使えません。
  • データを格納するために大量のメモリが必要です。
    • 32bitのint型で表現出来る全ての数をソートしようとしたなら、範囲は「-2,147,483,648～2,147,483,647」なので「4294967296個」のメモリ領域が必要になります。
  • データに同じ数値が重複してる場合には、数値と配列の添字を関連付けるような単純なデータ構造にすることができません。

C言語によるビンソートのプログラム


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

#define DATA_SIZE 32

/*!
 * @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/out]  array  整列する要素配列
 * @param[in]      size   配列のサイズ
 * @return         0      success
 * @return         -1     failure
 */
int
bin_sort(int *array, unsigned int size)
{
    int bin_array[DATA_SIZE];
    int cnt = 0;
    int idx = 0;

    /* ビンより大きい配列は処理できない */
    if(size > DATA_SIZE){
        printf("ERROR: bin_sort(): too much data size=%d\n", size);
        return(-1);
    }

    /* ビンを初期化する */
    for(cnt = 0; cnt < DATA_SIZE; cnt++){
        bin_array[cnt] = -1;
    }

    /* データをビンに格納する */
    for(cnt = 0; cnt < size - 1; cnt++){
        bin_array[array[cnt]] = array[cnt];
    }

    /* ビンの先頭から値を取り出して整列する */
    for(cnt = 0; cnt < DATA_SIZE; cnt++){
        if(bin_array[cnt] != -1){
            array[idx] = bin_array[cnt];
            idx++;
        }
    }
    return(0);
}

int
main(void)
{
    int data[] ={6,1,3,2,4,9,7,5,8,10};

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

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

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

    return(0);
}

関連ページ