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



ビンソート (bin sort)

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

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


ビンソートの整列過程

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


(手順1) データ自体の値を添字にして配列に格納します。

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

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


ビンソートの性能

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

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

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


ビンソートの問題点

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


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);
}

関連ページ



スポンサード リンク