バケットソート

鳩の巣ソート(pigeonhole sort)なんていうのがあるらあしいですよ。
でもバケットソートの方が一般的だし、効率も良いよ。

[計算時間]
O(n)

高速、安定ソート

[bucket_sort.c]

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

#define N 10 /* データ件数 */

int sort[N];
int list[N];
void BucketSort(void);
void output(int data[],char *name);

void BucketSort(void){
    int i,j,key=0;
    int counter[N] = {0};
    for(i = 0; i < N; i++){
        counter[list[i]] += 1;
    }
    for(i = 0; i < N; i++){
        for(j = 0; j < counter[i]; j++){
           sort[key++] = i; 
        }
    }
}

int main(void){
    int i;
    clock_t start,end;
    
    srand((unsigned int) time(NULL));
    for(i=0; i< N; i++){
        list[i]  = (int) rand() % 10 ;
    }

    printf("Stundy...\n");
    output(list,"before");

    printf("Start...\n");
    start = clock();

    BucketSort();

    end = clock();
    printf("End...\n");
    output(sort,"after");
    printf("Time:%.2f\n",(double)(end-start)/CLOCKS_PER_SEC);

    return EXIT_SUCCESS;
}


void output(int data[],char *name){
    int i=0;
    printf("%s => [",name);
    while(1){
        printf("%d",data[i]); 
        if (i != N - 1) {
            printf(",");
        }
        else{
            printf("]\n"); break;
        }
        ++i;
    }
}

データ10件の実行結果

Stundy...
before => [2,9,5,5,6,1,4,8,8]
Start...
End...
after => [0,1,2,4,5,5,6,8,8]
Time:0.00

データ100万件の実行結果

Stundy...
Start...
End...
Time:0.05

これまでのソートの中で最速。

なんでバケツソート？と思いますが
週末スリープソートに挫折したのと（特にpthredが上手く使えなくて）
日頃よく似た様なことやっている気がしたから。
スリープソートはバケットソートのバケツをメモリ空間の代わりに時間に置き換えたもの。
次回はスリープソート。実用性は低そうだけどね！