Heap sort in C

heap_sort.c

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

typedef int TYPE;
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 swap(TYPE* data, UINT n, UINT m){
    TYPE t = data[n];
    data[n] = data[m];
    data[m] = t;
}

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

void make_data_1(UINT num,TYPE* data){
    UINT i;
    for(i=0;i<num;i++){
        data[i]=i;
    }
    shuffle(num,data);
    debug(num,data);
}

void make_data_2(UINT num,TYPE* data){
    UINT i;
    for(i=0;i<num;i++){
        data[i]=i%10;
    }
    shuffle(num,data);
    debug(num,data);
}

void make_data_3(UINT num,TYPE* data){
    UINT i;
    for(i=0;i<num;i++){
        data[i]=num-i;
    }
    debug(num,data);
}


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

int is_heap(int i, int idx, TYPE* data){
    int j = (i+1)*2;

    if(j-1<idx){
        if(data[i]>=data[j-1]){
            if(!is_heap(j-1,idx,data))
                return 0;
        }else{
            return 0;
        }
    }else{
        return 1;
    }

    if(j<idx){
        if(data[i]>=data[j]){
            if(!is_heap(j,idx,data))
                return 0;
        }else{
            return 0;
        }
    }else{
        return 1;
    }

    return 1;
}

void up_heap(int idx, TYPE* data){
    int j;
    while(0<idx){
        j=(idx-1)/2;
        if(data[j]<data[idx])
            swap(data,j,idx);
        idx=j;
    }
}

void down_heap(int idx, TYPE* data){
    swap(data,0,idx);

    int i=0,j;
    while(1){
        j = (i+1)*2;

        if(j<idx){

            int l,u;
            if(data[j-1]<data[j]){
                u=j;
                l=j-1;
            }else{
                u=j-1;
                l=j;
            }

            if(data[i]<data[u]){
                swap(data,i,u);
                i=u;
            }else if(data[i]<data[l]){
                swap(data,i,l);
                i=l;
            }else{
                break;
            }
 
        }else if(j-1<idx){

            if(data[i]<data[j-1]){
                swap(data,i,j-1);
                i=j-1;
            }else{
                break;
            }
 
        }else{

            break;

        }
    }
}

void hs(int num, TYPE* data){
    int idx = 0;

    while(idx<num){
        up_heap(idx++,data);
        //assert(is_heap(0,idx-1,data));
    }

    while(0<idx){
        down_heap(--idx,data);
        //assert(is_heap(0,idx,data));
    }
}

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

    make_data_1(num,data);
    gettimeofday(&s,NULL);
    hs(num,data);
    gettimeofday(&e,NULL);
    printf("Heap sort (randomized sequential values): %.2lf sec.\n",print_time(&s,&e));
    assert(is_sorted(num,data));

    make_data_2(num,data);
    gettimeofday(&s,NULL);
    hs(num,data);
    gettimeofday(&e,NULL);
    printf("Heap sort (10 redundant values): %.2lf sec.\n",print_time(&s,&e));
    assert(is_sorted(num,data));

    make_data_3(num,data);
    gettimeofday(&s,NULL);
    hs(num,data);
    gettimeofday(&e,NULL);
    printf("Heap sort (Reversed sequential values): %.2lf sec.\n",print_time(&s,&e));
    assert(is_sorted(num,data));

    return 0;
}

$ gcc -W -O3 heap_sort.c -o heap_sort
$ ./heap_sort 100000000
Heap sort (randomized sequential values): 97.49 sec.
Heap sort (10 redundant values): 18.83 sec.
Heap sort (Reversed sequential values): 20.75 sec.