****main****
#include "SelectionSort.h"
#include "MergeSort.h"
#include "HeapSort.h"
#include "Quicksort.h"
#include <fstream>
#include <ctime>

//#include <vector>

int main()
{
    unsigned int size = 10000000;
    ifstream inFile("numbers.txt");
    inFile >> size;
    unsigned int * nums = new unsigned int[size];
    for (int i = 0; i < size; i++)
    {
        inFile >> nums[i];
        //cout << "number " << i << ": " << nums[i] << endl;
    }

    inFile.close();

    Sort obj(size);
    Merge obj2(size);
    Heap obj3(size);
    Quick obj4(size);

    clock_t startTime, endTime;

    startTime = clock();
    //obj4.quickSort(nums, 0, size-1);
    obj3.heapSort(nums, size);
    //obj2.mergeSort(nums, 0, size - 1);
    //obj.selectionSort(nums, size);
    endTime = clock();

    ofstream outFile("numbersNew.txt");
    for(int i = 0; i < size; i++)
    {
        outFile << nums[i] << endl;
    }
    outFile.close();

    cout << "Sort took: " << endTime - startTime << " milliseconds" << endl;
//
//    //for (int i = 0; i < size; i++)
//    //    cout << nums[i] << endl;

    return 0;
}

****selectionSort.h****
//I got this algorithm from geeksforgeeks.org
#include <iostream>
using namespace std;

class Sort
{
private:
    unsigned int * list;
    unsigned int numItems;
//

public:
    Sort()
    {
        numItems = 0;
        list = new unsigned int[numItems];
    }
    Sort(int cap)
    {
        numItems = cap;
        list = new unsigned int[numItems];
    }
    void swap(unsigned int *x, unsigned int *y)
    {
        int temp = *x;
        *x = *y;
        *y = temp;
    }

    void selectionSort(unsigned int * elements, int size)
    {
        int minIndex;
        for (int i = 0; i < size-1; i++) //traverse through the unsorted array to hold the current min
        {

            minIndex = i;
            //A second iterator traverses the array looking for an elements smaller than the current min, if it does so then min will be set to the new current min.
            for(int j = i+1; j < size; j++)
            {

                if(elements[j] < elements[minIndex])
                {
                    minIndex = j;
                }
            }
            //swap the current min with the new min
            swap(&elements[minIndex], &elements[i]);
        }

    }

    /* Function to print an array */
    void printArray(unsigned int * elements, int size)
    {
        for(int i = 0; i < size; i++)
        {
            cout << elements[i] << endl;
        }
    }


};

****MergeSort****
//I got this algorithm from geeksforgeeks.org
#include <iostream>
using namespace std;
class Heap
{
private:
    unsigned int * list;
    unsigned int numItems;

public:
    Heap()
    {
        numItems = 0;
        list = new unsigned int[numItems];
    }
    Heap(int cap)
    {
        numItems = cap;
        list = new unsigned int[numItems];
    }
    void heapify(unsigned int * elements, int n, int i)
    {
        int largest = i;  // Initialize largest as root
        int l = 2*i + 1;  // left = 2*i + 1
        int r = 2*i + 2;  // right = 2*i + 2

        // If left child is larger than root
        if (l < n && elements[l] > elements[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && elements[r] > elements[largest])
            largest = r;

        // If largest is not root
        if (largest != i)
        {
            swap(elements[i], elements[largest]);

            // Recursively heapify the affected sub-tree
            heapify(elements, n, largest);
        }
    }

    void heapSort(unsigned int * elements, int n)
    {
        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(elements, n, i);

        // One by one extract an element from heap
        for (int i=n-1; i>=0; i--)
        {
            // Move current root to end
            swap(elements[0], elements[i]);

            // call max heapify on the reduced heap
            heapify(elements, i, 0);
        }
    }

    void printArray(unsigned int * elements, int size)
    {
        for (int i = 0; i < size; i++)
        {
            cout << elements[i] << endl;
        }
    }


};

****QuickSort.h****
#include <iostream>
using namespace std;

class Quick
{
private:
    unsigned int numItems;
    unsigned int * list;

    void swap(unsigned int * x, unsigned int * y)
    {
        int temp = *x;
        *x = *y;
        *y = temp;
    }
public:
    Quick()
    {
        numItems = 0;
        list = new unsigned int[numItems];
    }
    Quick(int cap)
    {
        numItems = cap;
        list = new unsigned int[numItems];
    }
    /* This function takes last element as pivot, places
     the pivot element at its correct position in sorted
     array, and places all smaller (smaller than pivot)
     to left of pivot and all greater elements to right
     of pivot */
    int partition (unsigned int * elements, int low, int high)
    {
        int pivot = elements[high];    // pivot
        int i = (low - 1);  // Index of smaller element

        for (int j = low; j <= high- 1; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (elements[j] <= pivot)
            {
                i++;    // increment index of smaller element
                swap(&elements[i], &elements[j]);
            }
        }
        swap(&elements[i + 1], &elements[high]);
        return (i + 1);
    }

    /* The main function that implements QuickSort
     arr[] --> Array to be sorted,
     low  --> Starting index,
     high  --> Ending index */
    void quickSort(unsigned int * elements, int low, int high)
    {
        if (low < high)
        {
            /* pi is partitioning index, arr[p] is now
             at right place */
            int pi = partition(elements, low, high);

            // Separately sort elements before
            // partition and after partition
            quickSort(elements, low, pi - 1);
            quickSort(elements, pi + 1, high);
        }
    }

    void printArray(unsigned int * elements, int size)
    {
        for (int i = 0; i < size; i++)
        {
            cout << elements[i] << endl;
        }
    }
};