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