/* sorts.c * * * notes: implement simple hash table, use k&r book * */ #include <stdio.h> #include <stdlib.h> #include <memory.h> #include <string.h> #include <time.h> #include <assert.h> #define ARR_SIZE 20 #define ARR_RANGE 10 #define ELEM_LINE 10 #define FNAME "sort.txt" #undef PRINT_FILE /* global */ FILE *out = NULL; /* function prototypes */ void insrt_sort(int *, int); void select_sort(int *, int); void bubble_sort(int *, int); void prnt_arr(int *, int); int *mk_rand_arr(int, int); void mergesort(int *, int, int); void merge(int *, int, int, int); /* merge sort, divide and conquer */ void mergesort(int a[], int low, int high) { int mid; if (low < high) { mid = (low + high) / 2; mergesort(a, low, mid); mergesort(a, mid + 1, high); merge(a, low, high, mid); } } /* http://en.allexperts.com/q/C-1587/Merge-Sort-C.htm */ void merge(int a[], int low, int high, int mid) { int i, j, k, c[ARR_SIZE]; i = low; j = mid + 1; k = low; while ( (i <= mid) && (j <= high) ) { if (a[i] < a[j]) c[k++] = a[i++]; else c[k++] = a[j++]; } while (i <= mid) c[k++] = a[i++]; while (j <= high) c[k++] = a[j++]; for (i = low; i < k; i++) a[i] = c[i]; } /* in every iteration an element is compared with all the elements before it */ void insrt_sort(int *arr, int elem) { int i, j, tmp; for (i = 1; i < elem; i++) { tmp = arr[i]; j = i - 1; /* tmp is compared to all elements that were already inserted and are in order */ while ( (j >= 0) && (tmp < arr[j]) ) { arr[j+1] = arr[j]; j--; } arr[j+1] = tmp; } } /* slow on nearly sorted array */ void select_sort(int *arr, int elem) { int i, j, tmp; for (i = 0; i < elem - 1; i++) for (j = i + 1; j < elem; j++) if (arr[i] > arr[j]) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } /* pretty fast on nearly sorted array with extra code */ void bubble_sort(int *arr, int elem) { int i, j, tmp; for (i = 0; i < elem; i++) for (j = 0; j < elem - i - 1; j++) { if (arr[j] > arr[j+1]) { tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } void prnt_arr(int *arr, int elem) { if (arr == NULL) fputs("nothing to print", stderr); #ifdef PRINT_FILE assert(out != NULL); int i; for (i = 1; i < elem + 1; i++) { fprintf(out, "%3d ", *(arr + i - 1) ); if ( (i % ELEM_LINE == 0) && i != 0) fprintf(out, "\n"); } fprintf(out, "\n"); #else int i; for (i = 1; i < elem + 1; i++) { printf("%3d ", *(arr + i - 1) ); if ( (i % ELEM_LINE == 0) && i != 0) printf("\n"); } printf("\n"); #endif } int *mk_rand_arr(int elem, int range) { assert(elem > 0); int *arr = (int *) malloc(sizeof(int) * elem); if (arr == NULL) { perror("malloc"); exit(-1); } int i; range++; for (i = 0; i < elem; i++) arr[i] = rand() % range; return arr; } int main(int argc, char **argv) { srand( (unsigned int ) time(NULL) ); int *arr = mk_rand_arr(ARR_SIZE, ARR_RANGE); #ifdef PRINT_FILE out = fopen(FNAME, "w"); if (out == NULL) { perror("fopen"); exit(-1); } #endif #ifdef PRINT_FILE fprintf(out, "unsorted:\n"); #else printf("unsorted:\n"); #endif prnt_arr(arr, ARR_SIZE); //bubble_sort(arr, ARR_SIZE); //select_sort(arr, ARR_SIZE); //insrt_sort(arr, ARR_SIZE); mergesort(arr, 0, ARR_SIZE - 1); #ifdef PRINT_FILE fprintf(out, "sorted:\n"); #else printf("sorted:\n"); #endif prnt_arr(arr, ARR_SIZE); #ifdef PRINT_FILE fclose(out); #endif return 0; }