/* This file contains a collection of sorting routines */

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

void Swap(int *Lhs, int *Rhs)
{
    int Tmp = *Lhs;
    *Lhs = *Rhs;
    *Rhs = Tmp;
}

void InterchangeSort(int A[], int N)
{
    int i, j;

    for (i = 0; i < N-1; i++)
        for (j = i+1; j < N; j++)
        {
            if (A[i] > A[j])
                Swap(&A[i], &A[j]);
        }
}

void InsertionSort(int A[], int N)
{
    int j, P;
    int Tmp;

    for(P = 1; P < N; P++)
    {
        Tmp = A[P];
        for(j = P; j > 0 && A[j - 1] > Tmp; j--)
            A[j] = A[j - 1];
        A[j] = Tmp;
    }
}

void Shellsort(int A[], int N)
{
    int i, j, Increment;
    int Tmp;

    for(Increment = N / 2; Increment > 0; Increment /= 2)
        for(i = Increment; i < N; i++)
        {
            Tmp = A[i];
            for(j = i; j >= Increment; j -= Increment)
                if(Tmp < A[j - Increment])
                    A[j] = A[j - Increment];
                else
                    break;
            A[j] = Tmp;
        }
}

int Partition(int a[], int low, int high)
{
    int left, right;
    int pivot_item;
    pivot_item = a[low];
    left = low;
    right = high;
    while (left < right)
    {
        /* Move left while item < pivot */
        while(a <= pivot_item)
            left++;
        /* Move right while item > pivot */
        while(a[right] > pivot_item)
            right--;
        if (left < right)
            Swap(&a, &a[right]);
    }
    /* right is final position for the pivot */
    a[low] = a[right];
    a[right] = pivot_item;
    return right;
}

void Qsort(int a[], int low, int high)
{
    int pivot;
    /* Termination condition! */
    if (high > low)
    {
        pivot = Partition(a, low, high);
        Qsort(a, low, pivot-1);
        Qsort(a, pivot+1, high);
    }
}

void Quicksort(int A[], int N)
{
    Qsort(A, 0, N - 1);
}


void Permute(int A[], int N)
{
    int i;

    for(i = 0; i < N; i++)
        A[i] = i;
    for(i = 1; i < N; i++)
        Swap(&A[i], &A[rand() % (i + 1)]);
}

void Checksort(int A[], int N)
{
    int i;
    for(i = 0; i < N; i++)
        if(A[i] != i)
            printf("Sort fails: %d %d\n", i, A[i]);
    printf("Check completed\n");
}

void Copy(int Lhs[], const int Rhs[], int N)
{
    int i;
    for(i = 0; i < N; i++)
        Lhs[i] = Rhs[i];
}

/*
#define MaxSize 100000
int Arr1[MaxSize];
int Arr2[MaxSize];
*/

int* CreateArray(int n)
{
    int* pArray = new int[n];

    return pArray;
}

int BinarySearch(int* pArray, int n, int key)
{
    int lo = 0, hi = n-1;
    int mid;

    while (lo <= hi)
    {
        mid = (lo+hi)/2;
        if (pArray[mid] > key)
        {
            hi = mid-1;
        }
        else
        {
            if (pArray[mid] < key)
            {
                lo = mid+1;
            }
            else
            {
                return mid;
            }
        }
    }
    return -1;
}

void DestroyArray(int* pArray)
{
    if (pArray)
    {
        delete []pArray;
    }
}

main()
{
    clock_t s, e;
    int MaxSize = 1000000;

    int *Arr1, *Arr2;

    Arr1 = CreateArray(MaxSize);
    Arr2 = CreateArray(MaxSize);

    Permute(Arr2, MaxSize);
 /* 
    Copy(Arr1, Arr2, MaxSize);
    s = clock();
    InterchangeSort(Arr1, MaxSize);
    e = clock();
    Checksort(Arr1, MaxSize);
    printf("interchange sort: %lf\n", ((double)e-s)/CLK_TCK);
*/
    Copy(Arr1, Arr2, MaxSize);
    s = clock();
    InsertionSort(Arr1, MaxSize);
    e = clock();
    Checksort(Arr1, MaxSize);
    printf("insertion sort %lf\n", ((double)e-s)/CLK_TCK);

    Copy(Arr1, Arr2, MaxSize);
    s = clock();
    Shellsort(Arr1, MaxSize);
    e = clock();
    Checksort(Arr1, MaxSize);
    printf("shell sort: %lf\n", ((double)e-s)/CLK_TCK);
/*
    Copy(Arr1, Arr2, MaxSize);
    s = clock();
    Quicksort(Arr1, MaxSize);
    e = clock();
    Checksort(Arr1, MaxSize);
    printf("quick sort: %lf\n", ((double)e-s)/CLK_TCK);
*/
    getch();

    return 0;
}