ランダムシャッフル　解答ページ | Programming Place Plus　アルゴリズムとデータ構造編【その他のアルゴリズム】　第２章

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

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

typedef void (*shuffle_func)(int*, size_t);

enum {
    ARRAY_SIZE = 3,
};
static const int INIT_ARRAY_DATA[ARRAY_SIZE] = {0, 1, 2};
static const int ARRAY_PATTURN[][ARRAY_SIZE] = {
    {0, 1, 2},
    {0, 2, 1},
    {1, 0, 2},
    {1, 2, 0},
    {2, 0, 1},
    {2, 1, 0},
};

static void test_run(shuffle_func func);
static void random_shuffle(int* array, size_t size);
static void random_shuffle_ex(int* array, size_t size);
static size_t search_patturn(const int* array, size_t size);

int main(void)
{
    srand( (unsigned int)time(NULL) );

    test_run( random_shuffle );
    test_run( random_shuffle_ex );

    return 0;
}

/*
    指定したシャッフル関数でテスト実行開始
*/
void test_run(shuffle_func func)
{
    static const size_t RUN_COUNT = 1000000;  // 実行回数

    int array[ARRAY_SIZE];
    size_t patturn_count[SIZE_OF_ARRAY(ARRAY_PATTURN)] = {0};
    size_t patturn_index;

    for( size_t i = 0; i < RUN_COUNT; ++i){
        memcpy( array, INIT_ARRAY_DATA, sizeof(INIT_ARRAY_DATA) );
        func( array, SIZE_OF_ARRAY(array) );
        patturn_index = search_patturn( array, SIZE_OF_ARRAY(array) );
        patturn_count[patturn_index]++;
    }

    for( size_t i = 0; i < SIZE_OF_ARRAY(patturn_count); ++i){
        printf("%zu: %zu  (%.1f%%)\n",
            i,
            patturn_count[i],
            (double)patturn_count[i] * 100.0 / RUN_COUNT
        );
    }
    printf("\n\n");
}

/*
    配列の要素をランダムシャッフルする（良くない方法）
*/
void random_shuffle(int* array, size_t size)
{
    for( size_t i = 0; i < size; ++i ){
        size_t a = rand() % size;
        size_t b = rand() % size;
        SWAP( int, array[a], array[b] );
    }
}

/*
    配列の要素をランダムシャッフルする（Fisher-Yates shuffle）
*/
void random_shuffle_ex(int* array, size_t size)
{
    for( size_t i = size; i > 1; --i ){
        size_t a = i - 1;
        size_t b = rand() % i;
        SWAP( int, array[a], array[b] );
    }
}

/*
    並び順のパターンを探す
*/
size_t search_patturn(const int* array, size_t size)
{
    for( size_t i = 0; i < SIZE_OF_ARRAY(ARRAY_PATTURN); ++i ){
        if(memcmp(array, ARRAY_PATTURN[i], sizeof(int)*ARRAY_SIZE) == 0){
            return i;
        }
    }

    assert(!"該当するパターンが見つからない");
    return ~0;
}