#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 timer_start;
unsigned int timer_end;
unsigned int millis;

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 Selection()
{
    unsigned short i,k,j;
    unsigned int max;
    for (i=0; i<N; i++)
    {
        k = i;
        max = A[i];
        for (j = i+1; j<N; j++)
        {
            if (A[j] > max)
            {
                k = j;
                max = A[j];
            }
        }
        A[k] = A[i];
        A[i] = max;
        cout << A[i] << endl;
     }
}

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

    N = 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();
            timer_start = GetTickCount();
            Selection();
            timer_end = GetTickCount();
            millis = timer_end - timer_start;
            cout << "Took " << millis << " ms\n" << endl;
        }
        break;
     case 2:
        cout << "Insertion Sort" << endl;
        for(short i=0; i<10; i++)
        {
            initMatrix();
        }
        break;
     case 4:
        cout << "Bubble Sort" << endl;
        break;
     case 5:
        cout << "Heap Sort" << endl;
        break;
     case 6:
        cout << "Merge Sort" << endl;
        break;
     case 7:
        cout << "Quick Sort" << endl;
        break;
    }

    return 0;
}