/* sorts.c
 *
 * Kamil Kaminski
 * kamilkss@gmail.com
 *
 * notes: implement heap sort
 * 
 */

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#define ARR_SIZE 100
#define ARR_RANGE 99
#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 print_arr(int *, int);
int *mk_rand_arr(int, int);
void mergesort(int *, int, int);
void merge(int *, int, int, int);
void shell_sort(int *, int);
int binary_search(int *, int, int, int);
void quicksort(int, int, int *);

/* came from CS202 project */
void quicksort(int low, int high, int *arr)
{
    int lo = low;
    int hi = high;
    int mid;

    if (high > low)
    {
        /* set midpoint */
        mid = arr[(low + high)/2];

        /* loop until base addr reaches end of the arr */
        while (lo <= hi)
        {
            /* seek until we find strings that need to be swapped */
            while ((lo < high) && (arr[lo] < mid))
                ++lo;

            while ((hi > low) && (arr[hi] > mid))
                --hi;

            /* swap */
            if (lo <= hi)
            {
                int tmp = arr[hi];
                arr[hi] = arr[lo];
                arr[lo] = tmp;

                ++lo;
                --hi;
            }
        }

        /* sort the left partition */
        if (low < hi)
            quicksort(low, hi, arr);

        /* sort the right partition */
        if (lo < high)
            quicksort(lo, high, arr);
    }
}

int binary_search(int *a, int low, int high, int target)
{
    while (low <= high)
    {
        int middle = low + (high - low) / 2;

        if (target < a[middle])
            high = middle - 1;
        else if (target > a[middle])
            low = middle + 1;
        else
            return middle;
    }

    return -1;
}

/* pg 62, k&r 2nd ANSI, running T(N) = O(N^3/2) */
void shell_sort(int *v, int n)
{
    int gap, i, j, temp;

    for (gap = n/2; gap > 0; gap /= 2)
        for (i = gap; i < n; i++)
            for (j = i-gap; j >= 0 && v[j] > v[j+gap]; j -= gap)
            {
                temp = v[j];
                v[j] = v[j+gap];
                v[j+gap] = temp;
            }
}

/* 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 swapped code */
void bubble_sort(int *arr, int elem)
{
    int i, j, tmp, swapped;
    
    for (i = 0; i < elem; i++)
    {
        swapped = 0;

        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;
                swapped = 1;
            }
        }

        /* is not swapped implies already sorted array */
        if (!swapped)
            break;
    }
}

void print_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");
        else
            fprintf(out, " ");
    }
    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");
        else
            printf(" ");
    }
    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
    print_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);
    //shell_sort(arr, ARR_SIZE);
    quicksort(0, ARR_SIZE, arr);

#ifdef PRINT_FILE
    fprintf(out, "sorted:\n");
#else
    printf("sorted:\n");
#endif
    print_arr(arr, ARR_SIZE);

#ifdef PRINT_FILE
    fclose(out);
#endif

    return 0;
}