ももの知恵の樹

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

ボゴソート (bogo sort)

ボゴソートとは、要素をランダムに並べ替えることで偶発的な一致を試みる整列アルゴリズムです。

データ列をランダムに並べ替え、順番に並んでるかを確認し、順番でなければ再度ランダムに並べ替えるという操作をソートが完了するまで行います。運まかせの整列方法であり、一発で終了する可能性もありますが、そうでない場面の方が圧倒的に多く、乱数によっては永遠に終わらない可能性もあります。


無限の猿定理（infinite monkey theorem）

無限の猿定理とは、ランダムに文字列を作り続ければ、どのような文字列であってもいつかはできあがるという定理です。「猿がタイプライターの鍵盤をいつまでもランダムに叩きつづければ、シェイクスピアの作品を打ち出す」という比喩に由来して名前が付けられています。


ボゴソートの性能

平均的な計算時間は「O(n * n!)」であり、非常に効率の悪いアルゴリズムとして知られている。また、安定ソートではありません。


C言語によるボゴソートのプログラム


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

/*!
 * @brief      要素要素を入れ替える
 * @param[in]  i  要素位置
 * @param[in]  j  要素位置
 */
static void
swap(int *i, int *j)
{
    int temp;

    temp = *i;
    *i   = *j;
    *j   = temp;
}

/*!
 * @brief          配列がソート済みであるか確認する。
 * @param[in/out]  array  要素配列
 * @param[in]      size   配列のサイズ
 * @return         1      ソート済みである。
 * @return         0      ソート済みでない。
 */
static int
is_sorted(int *array, unsigned int size)
{
    int cnt;

    /* 要素が昇順であるか確認する */
    for(cnt = 0; cnt < (size - 1); cnt++){
        if(array[cnt] > array[cnt+1]) return(0);
    }
    return(1);
}

/*!
 * @brief          ボゴソートを行う。
 * @param[in/out]  array  整列する要素配列
 * @param[in]      size   配列のサイズ
 */
void
bogo_sort(int *array, unsigned int size)
{
    int x, y;
    int cnt = 1;

    while(1){
        /* 整列されているか確認する */
        if(is_sorted(array, size)) return;

        /* 要素を並び替える */
        x = rand() % size;
        y = rand() % size;
        swap(&array[x], &array[y]);

        printf("[%5d] :", cnt); array_print(array, size);
        cnt++;
    }
}

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

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

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

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

    return(0);
}

関連ページ