DS project 2: sortcomp.c

sortcomp.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <getopt.h>
#include <stdbool.h>

int int_data[1000000];
char* str_data[1000000];
void* temp[1000000];

/* a, b included */
int randint(const int a, const int b) {
    return (rand() % (b-a+1) + a);
}

bool is_digit(const char* c) {
	for (int i=0; i<strlen(c); i++)
		if (c[i] < '0' || c[i] > '9')
			return false;
	return true;
}

void swap(void* a, void* b, size_t size) {
    void * temp = malloc(size);
    
    memcpy(temp, a, size);
    memcpy(a, b, size);
    memcpy(b, temp, size);
    
    free(temp);
}

int compare_int(const void* a, const void* b) {
    return (*(int*)a - *(int*) b);
}

int compare_str(const void* a, const void* b) {
    return strcmp((char*) a, (char*) b);
}

void bubblesort(void* base, size_t num , size_t size, int (*comp)(const void*, const void*)) {
    /*
    for (int i=0; i<num-1; i++)
        for (int j=0; j<num-i-1; j++)
            if (base[j] > base[j+1])
                swap(base[j], base[j+1]);
    */
    for (int i=0; i<num-1; i++)
        for (int j=0; j<num-i-1; j++)
            if (comp((base + size*j), (base + size*(j+1))) > 0)
                swap((base + size*j), (base + size*(j+1)), size);
}

void insertionsort(void* base, size_t num, size_t size, int (*comp)(const void*, const void*)) {
    /*
    for (int i=0; i<num; i++) {
        int j = i;
        while (j >= 1 && base[j-1] > base[j]) {
            swap(base[j-1], base[j]);
            j--;
        }
    }
    */
    for (int i=0; i<num; i++) {
        int j = i;
        while (j >= 1 && comp((base + size*(j-1)), (base + size*j)) > 0) {
            swap((base + size*(j-1)), (base + size*j), size);
            j--;
        }
    }
}

void selectionsort(void* base, size_t num, size_t size, int (*comp)(const void*, const void*)) {
    /*
    for (int i=0; i<num-1; i++)
        for (int j=i+1; j<num; j++)
            if (base[j] > base[i])
                swap(base[j], base[i]);
    */
    for (int i=0; i<num-1; i++)
        for (int j=i+1; j<num; j++)
            if (comp((base + size*j), (base + size*i)) < 0)
                swap((base + size*j), (base + size*i), size);
}

void print_help() {
    puts("sortcomp");
    puts("\t-l: to specify the length of the data assuming that the data is of string type.");
    puts("\t-t: to define the type of the data, 's' for string, 'n' for number.");
    puts("");
    puts("Example:");
    puts("sortcomp -t n");
    puts("\tmeans your data type is number.");
    puts("sortcomp -l 7 -t s");
    puts("\tmeans your data type is string, and length is 7.");
}

int main(int argc, char* argv[]) {
    srand(time(NULL));
    
    int flag_t = -1; /* 0: number; 1: str*/
    int flag_l = -1;
    
    char c;
    while ((c = getopt(argc, argv, "t:l:")) != -1) {
        switch (c) {
            case 't':
                if (strcmp(optarg, "n") == 0)
                    flag_t = 0;
                else if (strcmp(optarg, "s") == 0)
                    flag_t = 1;
                break;
                
            case 'l':
				if (is_digit(optarg) == false) {
					print_help();
					return 0;
				}
                flag_l = atoi(optarg);
                break;
            default:
                print_help();
                return 0;
        }
    }
    
    if (flag_t == -1 || flag_l == 0 || (flag_t == 0 && flag_l != -1)) {
        print_help();
        return 0;
    }
    
    
    void* data;
    int data_size;
    int (*comp) (const void*, const void*);
	if (flag_t == 0) {
		for (int i=0; i<1000000; i++)
			int_data[i] = randint(-10000000, +10000000);
		
		data = int_data;
		data_size = sizeof(int);
		comp = compare_int;
	}
	else {
		const char set[] = {'A','B','C','D','E','F','G','H','I','J','K',
		'L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','a',
		'b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q',
		'r','s','t','u','v','w','x','y','z','0','1','2','3','4','5','6',
		'7','8','9'};
		for (int i=0; i<1000000; i++) {
			str_data[i] = (char*) malloc (sizeof(char) * (flag_l+1));
			str_data[i][flag_l] = 0;
			for (int j=0; j<flag_l; j++)
				str_data[i][j] = set[randint(0, 26+26+10-1-1)];
		}
		
		data = str_data;
		data_size = sizeof(char*);
		comp = compare_str;
	}

	puts("data size  bubble      selection   insertion   quick       merge");
	puts("--------------------------------------------------");
	for (int size=10; size <= 1000000; size *= 10) {
		printf("%-11d", size);
		
		if (size <= 1000) {	
			memcpy(temp, data, data_size*size);
			clock_t s1 = clock();
			bubblesort(temp, size, data_size, comp);
			clock_t e1 = clock();
			
			memcpy(temp, data, data_size*size);
			clock_t s2 = clock();
			insertionsort(data, size, data_size, comp);
			clock_t e2 = clock();
			
			memcpy(temp, data, data_size*size);
			clock_t s3 = clock();
			selectionsort(data, size, data_size, comp);
			clock_t e3 = clock();
			
			printf("%.6lf    ", (double)(e1-s1)/CLOCKS_PER_SEC);
			printf("%.6lf    ", (double)(e2-s2)/CLOCKS_PER_SEC);
			printf("%.6lf    ", (double)(e3-s3)/CLOCKS_PER_SEC);
		}
		else {
			printf("%-8s    ", "N/A");
			printf("%-8s    ", "N/A");
			printf("%-8s    ", "N/A");
		}
		
		memcpy(temp, data, data_size*size);
		clock_t s4 = clock();
		qsort(data, size, data_size, comp);
		clock_t e4 = clock();
		
		memcpy(temp, data, data_size*size);
		clock_t s5 = clock();
		mergesort(data, size, data_size, comp);
		clock_t e5 = clock();
		
		printf("%.6lf    ", (double)(e4-s4)/CLOCKS_PER_SEC);
		printf("%.6lf    ", (double)(e5-s5)/CLOCKS_PER_SEC);
		printf("\n");
	}
	    

    return 0;
}