#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <windows.h>

using namespace std;

// Pointer to A matrix. Matrix still does not exist.
unsigned int * A;

// N length of A matrix. 0 to 65535.
unsigned short N;

unsigned int timerStart;
unsigned int timerEnd;
unsigned int sumMillis;
unsigned int sumcompCounter;

void initMatrix()
{
    // Initialize A matrix with random integers in the range <1, 200.000>
    for(unsigned short i=0; i<N; i++)
    {
        A[i] = rand() % 200000 + 1;
        //cout << A[i] << endl;
    }
}

void SelectionSort()
{
    unsigned short i, j, first;
    unsigned int key;

    for (i= N - 1; i > 0; i--)
    {
        first = 0;
        for (j=1; j<=i; j++)
        {
            if (A[j] < A[first])
            {
                sumcompCounter++; // Increment the comparisons
                first = j;
            }
        }
        key = A[first];
        A[first] = A[i];
        A[i] = key;
    }
}

void InsertionSort()
{
    unsigned short i,j;
    unsigned int key;

    for (i=1; i<N; i++)
    {
        j = i;
        while (j>0 && A[j]>A[j-1])
        {
            sumcompCounter++; // Increment the comparisons
            key=A[j];
            A[j]=A[j-1];
            A[j-1]=key;
            j--;
        }
    }

    for (i=0; i<N;i++)
        cout << A[i] << endl;
    cout << "" << endl;
}

void BubbleSort()
{
    unsigned short i, j, flag = 1;
    unsigned int temp;

    for(i = 1; (i <= N) && flag; i++)
    {
        flag = 0;
        for (j=0; j < (N-1); j++)
        {
            if (A[j+1] > A[j])
            {
                sumcompCounter++; // Increment the comparisons
                temp = A[j];
                A[j] = A[j+1];
                A[j+1] = temp;
                flag = 1;
            }
        }
    }

    for(j=0; j<N; j++)
        cout << A[j] << endl;
    cout << "" << endl;
}

int main()
{
    // Initialize random seed
    srand ( time(NULL) );

    N = 0;
    sumMillis = 0;
    sumcompCounter = 0;

    short menuItem = 0;
    cout << "======================" << endl;
    cout << "         MENU         " << endl;
    cout << "======================" << endl;
    cout << "1. Selection Sort     " << endl;
    cout << "2. Insertion Sort     " << endl;
    cout << "3. Exit               " << endl;
    cout << "4. Bubble Sort        " << endl;
    cout << "5. Heap Sort          " << endl;
    cout << "6. Merge Sort         " << endl;
    cout << "7. Quicksort          " << endl;

    while(menuItem < 1 || menuItem > 7)
    {
        cout << "\nPlease enter your choice(1 to 7): ";
        cin >> menuItem;
    }

    if(menuItem==3)
    {
        cout << "Bye bye!" << endl;
        return 0;
    }

    // For performance reasons do not allow the user to enter a big length.
    while(N<=0 || N>255)
    {
        cout << "Now please enter the length of A matrix(1 to 255): ";
        cin >> N;
    }

    // Allocate N unsigned integers
    A = new unsigned int[N];

    switch (menuItem)
    {
     case 1:
        cout << "\nSelection Sort" << endl;
        cout << "==============" << endl;
        for(short i=0; i<10; i++)
        {
            initMatrix();
            timerStart = GetTickCount();
            SelectionSort();
            timerEnd = GetTickCount();
            sumMillis += timerEnd - timerStart; // Save execution time.
        }
        cout << "Average execution time " << sumMillis/10 << " ms" << endl;
        cout << "Average comparisons " << sumcompCounter/10 << endl;
        break;
     case 2:
        cout << "Insertion Sort" << endl;
        cout << "==============" << endl;
        for(short i=0; i<10; i++)
        {
            initMatrix();
            timerStart = GetTickCount();
            InsertionSort();
            timerEnd = GetTickCount();
            sumMillis += timerEnd - timerStart; // Save execution time.
        }
        cout << "Average execution time " << sumMillis/10 << " ms" << endl;
        cout << "Average comparisons " << sumcompCounter/10 << endl;
        break;
     case 4:
        cout << "Bubble Sort" << endl;
        cout << "==============" << endl;
        for(short i=0; i<10; i++)
        {
            initMatrix();
            timerStart = GetTickCount();
            BubbleSort();
            timerEnd = GetTickCount();
            sumMillis += timerEnd - timerStart; // Save execution time.
        }
        cout << "Average execution time " << sumMillis/10 << " ms" << endl;
        cout << "Average comparisons " << sumcompCounter/10 << endl;
        break;
     case 5:
        cout << "Heap Sort" << endl;
        cout << "==============" << endl;
        break;
     case 6:
        cout << "Merge Sort" << endl;
        cout << "==============" << endl;
        break;
     case 7:
        cout << "Quick Sort" << endl;
        cout << "==============" << endl;
        break;
    }

    return 0;
}