Bucket sort

bucket.c

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

int cmp(const void* a, const void* b){
    if(*(double*)a<*(double*)b) return -1;
    if(*(double*)a>*(double*)b) return 1;
    return 0;
}

double print_time(struct timeval *s, struct timeval *e){
    int si = (s->tv_sec%1000000)*1000+s->tv_usec/1000;
    int ei = (e->tv_sec%1000000)*1000+e->tv_usec/1000;
    return (double)(ei-si)/1000.0;
}

void swap(double* data, int n, int m){
    double t = data[n];
    data[n] = data[m];
    data[m] = t;
}

void shuffle(int num, double* data){
    int i,n,m,t;
    srand(0);
    i=n=m=0;
    t=data[i];
    while(i<2*num){
        m=rand()%num;
        swap(data,n,m);
        n=m;
        i++;
    }
}

void make_data_1(int num, double* data){
    int i;
    srand(0);
    for(i=0;i<num;i++){
        data[i] = (rand()%num)/(double)num;
    }
}

void make_data_2(int num, double* data){
    int i;
    for(i=0;i<num;i++){
        data[i] = i/(double)num;
    }
    shuffle(num,data);
}


typedef struct entry {
    double val;
    struct entry* next;
} entry;

typedef struct bucket {
    int size;
    entry* head;
} bucket;

entry* take_last(entry* head){
    if(head->next == NULL){
        return head;
    }else{
        return take_last(head->next);
    }
}

void fill_buckets(int num, double* data, bucket* buckets, entry* lists){
    int i,k;
    k=0;
    for(i=0;i<num;i++){
        int n = data[i]*num;
        //entry* e = malloc(sizeof(entry));
        entry* e = &lists[k++];
        e->val = data[i];
        e->next = NULL;

        if(buckets[n].head == NULL){
            buckets[n].head = e;
        }else{
            entry* last = take_last(buckets[n].head);
            last->next = e;
        }
        buckets[n].size++;
    }
}

void insert_sort(int num, double* data, bucket* buckets){
    int i,j,k,n,m;
    n=0;
    m=0;
    for(i=0;i<num;i++){
        if(buckets[i].size==0) continue;
        entry* e = buckets[i].head;
        int size = buckets[i].size;
        while(e!=NULL){
            data[n++] = e->val;
            e = e->next;
        }
        for(j=n-size;j<n;j++){
            for(k=j-1;k>=n-size;k--){
                if(data[k+1]<data[k]){
                    swap(data,k,k+1);
                }
            }
        }
    }
}

void bs(int num, double* data, bucket* buckets, entry* lists){
    fill_buckets(num,data,buckets,lists);
    insert_sort(num,data,buckets);
}

// in_place_quick_sort
void qs(int num, double* data){
    if(num==1) return;
    swap(data,0,num/2);
    double m = data[0];
    int i,j;
    i=1; j=num-1;
    for(;;){
        while(data[i]<m&&i<=num){i++;}
        while(data[j]>m){j--;}
        if(i>j) break;
        swap(data,i++,j--);
    }
    swap(data,0,j);
    if(j>0)
        qs(j,data);
    if(i<num)
        qs(num-i,data+i);
}

int is_sorted(int num, double* data){
    int i=0;
    for(i=0;i<num-1;i++){
        if(data[i]>data[i+1]) return 0;
    }
    return 1;
}

void debug(int num, double* data){
    if(num>100) return;
    int i;
    for(i=0;i<num;i++){
        printf("%f,",data[i]);
    }
    printf("\n");
}

int main(int argc, char* argv[]){
    if(argc!=2) return 1;
    int num = atoi(argv[1]);
    double* data = malloc(sizeof(double)*num);
    struct timeval s, e;

    make_data_1(num,data);
    gettimeofday(&s,NULL);
    qsort(data,num,sizeof(double),cmp);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    printf("Library qsort() with random floating points [0-1): %.2lf sec.\n",print_time(&s,&e));

    make_data_2(num,data);
    gettimeofday(&s,NULL);
    qsort(data,num,sizeof(double),cmp);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    printf("Library qsort() with randomized sequential floating points [0-1): %.2lf sec.\n",print_time(&s,&e));


    make_data_1(num,data);
    gettimeofday(&s,NULL);
    qs(num,data);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    printf("In place quick sort with random floating points [0-1): %.2lf sec.\n",print_time(&s,&e));

    make_data_2(num,data);
    gettimeofday(&s,NULL);
    qs(num,data);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    printf("In place quick sort with randomized sequential floating points [0-1): %.2lf sec.\n",print_time(&s,&e));


    bucket* buckets;
    entry* lists;

    buckets = calloc(num,sizeof(bucket));
    lists = calloc(num,sizeof(entry));

    make_data_1(num,data);
    debug(num,data);
    gettimeofday(&s,NULL);
    bs(num,data,buckets,lists);
    gettimeofday(&e,NULL);
    debug(num,data);
    assert(is_sorted(num,data));
    free(buckets);
    free(lists);
    printf("Bucket sort with random floating points [0-1): %.2lf sec.\n",print_time(&s,&e));

    buckets = calloc(num,sizeof(bucket));
    lists = calloc(num,sizeof(entry));

    make_data_2(num,data);
    gettimeofday(&s,NULL);
    bs(num,data,buckets,lists);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    free(buckets);
    free(lists);
    printf("Bucket sort with randomized sequential floating points [0-1): %.2lf sec.\n",print_time(&s,&e));

    return 0;
}

$ gcc -W -O3 bucket.c -o bucket
$ ./bucket 100000000
Library qsort() with random floating points [0-1): 20.85 sec.
Library qsort() with randomized sequential floating points [0-1): 20.74 sec.
In place quick sort with random floating points [0-1): 12.68 sec.
In place quick sort with randomized sequential floating points [0-1): 12.99 sec.
Bucket sort with random floating points [0-1): 20.80 sec.
Bucket sort with randomized sequential floating points [0-1): 10.59 sec.