Run sort algorithms with randomized single data

sorts.c

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

void print(int* a, int n){
        int i=0;
        printf("[");
        for(i=0;i<(n>100?100:n);i++){
                if(i>0) printf(",");
                printf("%d",*(a+i));
        }
        if(n>100) printf("...");
        printf("]\n");
}

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;
}

int* sample(int n){
        int* sample_data = (int*)malloc(sizeof(int)*n);
        int i=0;
        int j=0;
        while(j<n){
                if(rand()%2){
                        *(sample_data+j) = i;
                        j++;
                        if(rand()%100){
                                i++;
                        }
                }else{
                        i++;
                }
        }
        return sample_data;
}

int* sample_input(int n, char** argv){
        int* sample_data = (int*)malloc(sizeof(int)*n);
        int i;
        for(i=0;i<n;i++){
                *(sample_data+i) = atoi(*(argv+i));
        }
        return sample_data;
}

int* shuffle(int* data, int n){
        int* random_data = (int*)malloc(sizeof(int)*n);
        memcpy(random_data,data,sizeof(int)*n);
        int s = rand()%n;
        int i, d, tmp;
        for(i=0;i<n;i++){
                d = rand()%n;
                tmp = *(random_data+d);
                *(random_data+d) = *(random_data+s);
                *(random_data+s) = tmp;
                s = d;
                //print(random_data,n);
        }
        return random_data;
}

int assert(int* a, int* b, int n){
        int i=0;
        if(memcmp(a,b,n)){
                return 0;
        }else{
                // memcmp returns 0 if they are same
                return 1;
        }
}

int* quick_sort(int *data, int n){

        int pivot = *data;
        int *sg = (int*)malloc(sizeof(int)*n); // small group
        int *lg = (int*)malloc(sizeof(int)*n); // large group

        int i;
        int sgi=0;
        int lgi=0;
        for(i=1;i<n;i++){
                if(*(data+i) < pivot){
                        *(sg+sgi) = *(data+i);
                        sgi++;
                }
        }
        for(i=1;i<n;i++){
                if(*(data+i) >= pivot){
                        *(lg+lgi) = *(data+i);
                        lgi++;
                }
        }

        int *sorted_sg, *sorted_lg;
        if(sgi>0){
                sg = quick_sort(sg,sgi);
        }
        if(lgi>0){
                lg = quick_sort(lg,lgi);
        }

        int *new = (int*)malloc(sizeof(int)*n);

        for(i=0;i<sgi;i++){
                *(new+i) = *(sg+i);
        }
        *(new+sgi) = pivot;
        for(i=0;i<lgi;i++){
                *(new+sgi+1+i) = *(lg+i);
        }

        free(sg);
        free(lg);

        return new;

}

int* merge_sort(int *data, int n){

        if(n==1){
                return data;
        }else{
                int *left = (int*)malloc(sizeof(int)*n);
                int *right = (int*)malloc(sizeof(int)*n);
                int half = n/2;

                int i;
                for(i=0;i<half;i++){
                        *(left+i) = *(data+i);
                }
                for(i=half;i<n;i++){
                        *(right+i-half) = *(data+i);
                }

                left = merge_sort(left,half);
                right = merge_sort(right,n-half);

                int left_idx=0;
                int right_idx=0;
                int *new = (int*)malloc(sizeof(int)*n);
                while(left_idx<half || right_idx<n-half){
                        if(left_idx == half){
                                *(new+left_idx+right_idx) = *(right+right_idx);
                                right_idx++;
                        }else if(right_idx == n-half){
                                *(new+left_idx+right_idx) = *(left+left_idx);
                                left_idx++;
                        }else if( *(left+left_idx) < *(right+right_idx) ){
                                *(new+left_idx+right_idx) = *(left+left_idx);
                                left_idx++;
                        }else{
                                *(new+left_idx+right_idx) = *(right+right_idx);
                                right_idx++;
                        }
                }

                free(left);
                free(right);

                return new;
        }

}

int* bubble_sort(int *data, int n){
        int i, tmp, m;
        m = n;
        while(m>1){
                for(i=0;i<m-1;i++){
                        if(*(data+i)>*(data+i+1)){
                                tmp = *(data+i+1);
                                *(data+i+1) = *(data+i);
                                *(data+i) = tmp;
                        }
                }
                m--;
        }
        return data;
}

void do_assert(int* data, int* random_data, int* sorted_data, int n){
        if(assert(sorted_data,data,n)){
                printf("Sorted check OK.\n");
        }else{
                print(data,n);
                print(random_data,n);
                print(sorted_data,n);

        }
}

int main(int argc, char *argv[]){
        //printf("%d\n",RAND_MAX);
        int n = atoi(argv[1]);
        int *sample_data;
        int* sorted_data;
        struct timeval s, e;

        if(argc>2){
                sample_data = sample_input(n,argv+2);

                gettimeofday(&s,NULL);
                sorted_data = quick_sort(sample_data,n);
                gettimeofday(&e,NULL);
                printf("Quick sort : %.2lf sec.\n",print_time(&s,&e));
                print(sorted_data,n);

                gettimeofday(&s,NULL);
                sorted_data = merge_sort(sample_data,n);
                gettimeofday(&e,NULL);
                printf("Merge sort : %.2lf sec.\n",print_time(&s,&e));
                print(sorted_data,n);

                if(n<=50000){
                        gettimeofday(&s,NULL);
                        sorted_data = bubble_sort(sample_data,n);
                        gettimeofday(&e,NULL);
                        printf("Bubble sort : %.2lf sec.\n",print_time(&s,&e));
                        print(sorted_data,n);
                }

        }else{
                sample_data = sample(n);
                int *random_data = shuffle(sample_data,n);

                gettimeofday(&s,NULL);
                sorted_data = quick_sort(random_data,n);
                gettimeofday(&e,NULL);
                printf("Quick sort : %.2lf sec.\n",print_time(&s,&e));
                do_assert(sample_data,random_data,sorted_data,n);

                gettimeofday(&s,NULL);
                sorted_data = merge_sort(random_data,n);
                gettimeofday(&e,NULL);
                printf("Merge sort : %.2lf sec.\n",print_time(&s,&e));
                do_assert(sample_data,random_data,sorted_data,n);

                if(n<=50000){
                        gettimeofday(&s,NULL);
                        sorted_data = bubble_sort(random_data,n);
                        gettimeofday(&e,NULL);
                        printf("Bubble sort : %.2lf sec.\n",print_time(&s,&e));
                        do_assert(sample_data,random_data,sorted_data,n);
                }

        }

        return 0;
}