極力遅いソーティング

プログラミング作法という本に極力遅いソーティングをしろという問題があったので
それを実装してみた。当然ながら適当なループで時間稼ぎとかはなしで、答えを求めるのが
遅いというものね。

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

static void late_sort(int n, int now, int *array);
static void check_order(int n, int *order);
static double gettimeofday_sec();
static void print_array(int n, int *p);
static int compare(const void *a, const void *b);

static int *array;
static double start, end;

int main(int argc, char *argv[])
{
    int i, array_num;
    int *order;

    if (argc < 2) {
        array_num = 10;
    } else {
        array_num = atoi(argv[1]);
    }

    array = (int *)malloc(sizeof(int) * array_num);
    if ( array == NULL ) {
        fprintf(stderr, "Error : allocate memory array\n");
        exit(EXIT_FAILURE);
    }

    order = (int *)malloc(sizeof(int) * array_num);
    if ( array == NULL ) {
        fprintf(stderr, "Error : allocate memory order\n");
        exit(EXIT_FAILURE);
    }

    for (i = 0; i < array_num; i++) {
        array[i] = rand() % 10;
    }
    print_array(array_num, array);

    start = gettimeofday_sec();
#ifdef LATE_SORT
    late_sort(array_num, 0 ,order);
#else
    qsort(array, array_num ,sizeof(int), compare);
    end = gettimeofday_sec();
    print_array(array_num, array);
    printf("time = %10.30f\n", end - start);
#endif

    return 0;
}

static void late_sort(int n, int now, int *order)
{
    int i, j;

    for (i = 0; i < n; i++) {
        int error = 0;

        for (j = 0; j < now; j++) {
            if (i == order[j]) {
                error = 1;
                break;
            }
        }

        if (error == 0) {
            order[now] = i;
            if (now == n - 1) {
                check_order(n, order);
            } else {
                late_sort(n, now + 1, order);
            }
        }
    }
}

static void check_order(int n, int *order)
{
    int i, prev;
    int *dummy;

    prev = array[ order[0] ];
    for (i = 0; i < n; i++) {
        if (prev < array[ order[i] ])
            return;

        prev = array[ order[i] ];
    }

    dummy = (int *)malloc(sizeof(int) * n);
    if ( array == NULL ) {
        fprintf(stderr, "Error : allocate memory dummy\n");
        exit(EXIT_FAILURE);
    }

    for (i = 0; i < n; i++) {
        dummy[i] = array[ order[i] ];
    }

    free(array);
    array = dummy;

    end = gettimeofday_sec();
    printf("time = %10.30f\n", end - start);

    print_array(n, array);

    exit(EXIT_SUCCESS);
}

static void print_array(int n, int *p)
{
    int i;

    printf("[");
    for (i = 0; i < n; i++) {
        printf("%d ", p[i]);
    }
    printf("]\n");
}

static double gettimeofday_sec()
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

static int compare(const void *a, const void *b)
{
    return *(int*)b - *(int*)a;
}

方針としてはソーティング対象になる配列のすべての並べ方を求めるというもの。
それで降順に並べられている順番があれば、その通り配列を並べ替える。
計算量的には配列長(n)の階乗に比例する.

参考のために標準ライブラリの qsortと比較してみた.
配列長は 10. 普通に考えると論外な数字だけど、それ以上伸ばすと
結構な時間がかかってしまう.

環境 Core2Duo 2.2GHz Memory 3GHz Ubuntu 9.0.4 Linux 2.6.28-15
コンパイラ GCC 4.3.3 最適化オプション O2

qsort     :  0.000020027160644531250000000000秒
late_sort :  1.068710961146280169486999511719秒

qsortに比べると約 53363倍遅い.
十分遅くなったと言えるのかな？

プログラミング作法