Multi-key quick sort in place for strings

multi_key_quick_sort.c

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

#define STRLEN 10
#define STRLENL 1000

typedef unsigned int UINT;

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 debug(UINT num, char** data){
    if(num>300) return;
    UINT i;
    for(i=0;i<num;i++){
        printf("%s,",data[i]);
    }
    printf("\n");
}

void make_data1(int num, char** data){
    int i,j;
    srand(0);
    for(i=0;i<num;i++){
        data[i] = malloc(sizeof(char)*(STRLEN+1));
        for(j=0;j<STRLEN;j++){
            char m = (char)(rand()%26+65);
            data[i][j]=m;
        }
        data[i][j]='\0';
    }
}

void make_data2(int num, char** data){
    int i,j;
    srand(0);
    for(i=0;i<num;i++){
        data[i] = malloc(sizeof(char)*(STRLEN+1));
        char m = (char)(rand()%26+65);
        for(j=0;j<STRLEN;j++){
            data[i][j]=m;
        }
        data[i][j]='\0';
    }
}

void make_data3(int num, char** data){
    int i,j;
    srand(0);
    for(i=0;i<num;i++){
        data[i] = malloc(sizeof(char)*(STRLEN+1));
        for(j=0;j<STRLEN;j++){
            char m = (char)(rand()%26+65);
            if(rand()%STRLEN>0){
                data[i][j]=m;
            }else{
                break;
            }
        }
        data[i][j]='\0';
    }
}

void make_data4(int num, char** data){
    int i,j;
    srand(0);
    for(i=0;i<num;i++){
        data[i] = malloc(sizeof(char)*(STRLENL+1));
        for(j=0;j<STRLENL;j++){
            char m = (char)(rand()%26+65);
            data[i][j]=m;
        }
        data[i][j]='\0';
    }
}

void clear(int num, char** data){
    int i;
    for(i=0;i<num;i++)
        free(data[i]);
}

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

int cmp1(char* a, char*b){
    return strcmp(a,b);
}

int cmp2(char* a, char*b, int n){
    return a[n]>b[n]?1:a[n]<b[n]?-1:0;
}

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

void qs(UINT num, char** data){
    if(num==1) return;
    swap(data,0,num/2);
    UINT i,k;
    k=1;
    for(i=1;i<num;i++){
        if(cmp1(data[0],data[i])>0)
            swap(data,k++,i);
    }
    swap(data,0,k-1);
    if(k-1>0)
        qs(k-1,data);
    if(k<num)
        qs(num-k,data+k);
}

void mkqs(UINT num, char** data, int n){
    if(num==1) return;
    swap(data,0,num/2);
    UINT i,k,p;
    k=p=1;
    for(i=1;i<num;i++){
        switch(cmp2(data[0],data[i],n)){
            case 1:
                swap(data,k,i);
                swap(data,p++,k++);
                break;
            case 0:
                swap(data,k++,i);
                break;
        }
    }
    swap(data,0,--p);
    if(p>0)
        mkqs(p,data,n);
    if(k-p>0)
        mkqs(k-p,data+p,n+1);
    if(k<num)
        mkqs(num-k,data+k,n);
}

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

    make_data1(num,data);
    gettimeofday(&s,NULL);
    qs(num,data);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    clear(num,data);
    printf("Quick sort with strings (random): %.2f sec\n",print_time(&s,&e));

    make_data2(num,data);
    gettimeofday(&s,NULL);
    qs(num,data);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    clear(num,data);
    printf("Quick sort with strings (redundant) : %.2f sec\n",print_time(&s,&e));

    make_data3(num,data);
    gettimeofday(&s,NULL);
    qs(num,data);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    clear(num,data);
    printf("Quick sort with strings (variable length) : %.2f sec\n",print_time(&s,&e));

    make_data4(num,data);
    gettimeofday(&s,NULL);
    qs(num,data);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    clear(num,data);
    printf("Quick sort with strings (100 times length) : %.2f sec\n",print_time(&s,&e));


    make_data1(num,data);
    gettimeofday(&s,NULL);
    mkqs(num,data,0);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    clear(num,data);
    printf("Multi-key Quick sort with strings (random) : %.2f sec\n",print_time(&s,&e));

    make_data2(num,data);
    gettimeofday(&s,NULL);
    mkqs(num,data,0);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    clear(num,data);
    printf("Multi-key Quick sort with strings (redundant) : %.2f sec\n",print_time(&s,&e));

    make_data3(num,data);
    gettimeofday(&s,NULL);
    mkqs(num,data,0);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    clear(num,data);
    printf("Multi-key Quick sort with strings (variable length) : %.2f sec\n",print_time(&s,&e));

    make_data4(num,data);
    gettimeofday(&s,NULL);
    mkqs(num,data,0);
    gettimeofday(&e,NULL);
    assert(is_sorted(num,data));
    clear(num,data);
    printf("Multi-key Quick sort with strings (100 times length) : %.2f sec\n",print_time(&s,&e));

    return 0;
}

$ ./multi_key_quick_sort 1000000
Quick sort with strings (random): 0.31 sec
Quick sort with strings (redundant) : 138.48 sec
Quick sort with strings (variable length) : 53.75 sec
Quick sort with strings (100 times length) : 0.88 sec
Multi-key Quick sort with strings (random) : 0.19 sec
Multi-key Quick sort with strings (redundant) : 0.45 sec
Multi-key Quick sort with strings (variable length) : 0.21 sec
Multi-key Quick sort with strings (100 times length) : 0.40 sec