// ================================================================
// FILE:    ArraySort.cpp
//
// AUTHOR:  Yee Hsu
//
// DATE:    November 11, 2000
//
// LIBRARIES:
//      iostream.h  --  standard steam I/O
//      ArraySort.h --  declaration of ArraySort class
//
// FUNCTIONS/METHODS DEFINED:
//  CONSTRUCTOR/DESTRUCTOR
//      Sort()                          --  default constructor
//      Sort(const Sort& s)             --  overloaded constructor
//      ~Sort()                         --  default destructor
//
//  OPERATOR OVERLOADS  
//      operator=(const Sort& s)        --  overloaded =
//
//  SORT LIST ADT
//      Push(const int nNum)            --  push onto FIFO stack
//      Pop()                           --  pop off FIFO stack
//      Display(const char[])           --  display the list
//      Swap(int&, int&)                --  swap two numbers
//
//  SORTING ALGORITHMS
//      BubbleSort()                    --  Bubble Sort
//      InsertionSort()                 --  Insertion Sort
//      SelectionSort()                 --  Selection Sort
//      MergeSort()                     --  MergeSort
//      QuickSort()                     --  QuickSort
//      HashSort()                      --  HashSort
//
//  HELPER SORTING ALGORITHMS
//      MergeSort(int, int)             --  Recursive MergeSort
//      MergeSort(int, int, int)        --  Merge list
//      QuickSort(int[], int, int)      --  Recursive QuickSort
// ================================================================

#include <iostream.h>
#include "ArraySort.h"

// ================================================================
// IDENTIFIER:  Sort()
//
// COMMENTS:    Sort default constructor.
// ================================================================

Sort::Sort() : nTop(-1)
{
    for (int i = 0; i < MAX_NUM; i++)
        nNumList[i] = EOD;
}

// ================================================================
// IDENTIFIER:  Sort(const Sort& s)
//
// PRE:         Needs a copy of the list
//
// POST:        An identical copy of the list
//
// PARAM:       &s  -- reference to the list
//
// COMMENTS:    Sort copy constructor. Makes a copy of the
//              sort list.
// ================================================================

Sort::Sort(const Sort& s)
{
    nTop = s.nTop;

    for (int i = 0; s.nNumList[i] != EOD; i++)
        nNumList[i] = s.nNumList[i];
}

// ================================================================
// IDENTIFIER:  ~Sort()
//
// PRE:         A list wich needs to be destroyed
//
// POST:        A list destroyed
//
// COMMENTS:    Sort destructor.
// ================================================================

Sort::~Sort()
{
    nTop = -1;

    for (int i = 0; i < MAX_NUM; i++)
        nNumList[i] = -1;
}

// ================================================================
// IDENTIFIER:  operator=(const Sort& s)
//
// PRE:         A list needs to be assigned to a list
//
// POST:        A copy of list to another list
//
// PARAM:       &s -- a reference to a list
//
// RETURNS:     *this   -- for concatenation
//
// COMMENTS:    sort assignment = overload. Enables = to
//              assign a list to a list.
// ================================================================

Sort& Sort::operator=(const Sort& s)
{
    if (this != &s)
    {
        this->~Sort();

        nTop = s.nTop;

        for (int i = 0; s.nNumList[i] != EOD; i++)
            nNumList[i] = s.nNumList[i];
    }
    return *this;
}

// ================================================================
// IDENTIFIER:  Push(const int nNum)
//
// PRE:         A number that needs to be pushed onto the stack
//
// POST:        A number pushed on top of the stack
//
// PARAM:       nNUm    --  the number to be pushed on the stack
//
// ALGORITHM:   Update the top pointer. Assign the number to
//              the top array.
//
// COMMENTS:    Pushes a number on top of the FIFO stack
// ================================================================

void Sort::Push(const int nNum)
{
    nNumList[++nTop] = nNum;
}

// ================================================================
// IDENTIFIER:  Pop()
//
// PRE:         A number that needs to be popped off the stack
//
// POST:        A number popped off the stack
//
// RETURN:      The number on top of the stack
//
// ALGORITHM:   Return the number on the top of the stack.
//              Decrement the top pointer.
//
// COMMENTS:    Pops a number off the FIFO stack
// ================================================================

int Sort::Pop()
{
    return nNumList[nTop--];
}

// ================================================================
// IDENTIFIER:  Display(const char sMsg[])
//
// PRE:         A need to display the contents in the list
//
// POST:        The list displayed
//
// PARAM:       sMsg[]  --  the message to display
//
// ALGORITHM:   Run through the stack list and display each
//              element until the list is empty.
//
// COMMENTS:    Displays the contents in the list array
// ================================================================

void Sort::Display(const char sMsg[])
{
    cout<<sMsg  <<endl;

    for (int i = 0; nNumList[i] != EOD; i++)
        cout<<nNumList[i]   <<" ";

    cout<<endl  <<endl;
}

// ================================================================
// IDENTIFIER:  Swap(int& nNum1, int& nNum2)
//
// PRE:         A need to swap two numbers
//
// POST:        Two number exchange places
//
// PARAM:       &nNum1  --  reference to 1st number
//              &num2   --  reference to 2nd number
//
// ALGORITHM:   Make a temporary integer. Store the first integer
//              to the temporary buffer. Assign the second number
//              to the first integer. Assign the buffer number
//              back to the second number.
//
// COMMENTS:    Swaps the contents of two numbers.
// ================================================================

void Sort::Swap(int& nNum1, int& nNum2)
{
    /*
    int temp = nNum1;
    nNum1 = nNum2;
    nNum2 = temp;
    */

    // fast algo
    nNum1 ^= nNum2 ^= nNum1 ^= nNum2;
}

// ================================================================
// IDENTIFIER:  BubbleSort()
//
// PRE:         A list that needs to be sorted
//
// POST:        A list that is sorted
//
// CALLS:       Swap(int&, int&)    --  the swap routine
//
// ALGORITHM:   Run through the list and compare each element to
//              the next element. If the 1st number is greater
//              than the 2nd number, swap them and continue to
//              bubble up the array, else the list is sorted
//
// EFFICIENCY   Best:       N
//              Average:    N^2
//              Worst:      N^2
//
// COMMENTS:    Sorts the array in ascending order using BubbleSort
// ================================================================

void Sort::BubbleSort()
{
    bool sorted = false;

    for (int i = 0; i < nTop && !sorted; i++)
    {
        sorted = true;

        for (int j = 0; j < nTop - i; j++)
        {
            if (nNumList[j] > nNumList[j+1])
            {
                Swap(nNumList[j], nNumList[j+1]);
                sorted = false;
            }
        }
    }
}

// ================================================================
// IDENTIFIER:  InsertionSort()
//
// PRE:         A list that needs to be sorted
//
// POST:        A list that is sorted
//
// ALGORITHM:   Run through the list. Take a number and assign
//              it to a temporary variable. Compare the 1st number
//              to the 2nd number. Loop and shift all numbers
//              down the array. Insert the number at the back.
//
// EFFICIENCY   Best:       N^2
//              Average:    N^2
//              Worst:      N^2
//
// COMMENTS:    Sorts the array in ascending order using
//              InsertionSort
// ================================================================

void Sort::InsertionSort()
{
    for (int i = 1; i <= nTop; i++)
    {
        int temp = nNumList[i];
        int j = i - 1;

        while (j >= 0 && nNumList[j] > temp)
            nNumList[j+1] = nNumList[j--];

        nNumList[j+1] = temp;
    }
}

// ================================================================
// IDENTIFIER:  SelectionSort()
//
// PRE:         A list that needs to be sorted
//
// POST:        A list that is sorted
//
// CALLS:       Swap(int&, int&)    --  swap routine
//
// ALGORITHM:   Run through the array and search for the largest
//              number. Swap it with the last position number
//              and repeat
//
// EFFICIENCY   Best:       N^2
//              Average:    N^2
//              Worst:      N^2
//
// COMMENTS:    Sorts the array in ascending order using
//              SelectionSort
// ================================================================

void Sort::SelectionSort()
{
    for (int i = nTop; i > 0; i--)
    {
        int nMax = 0;

        for (int j = 1; j <= i; ++j)
        {
            if (nNumList[j] > nNumList[nMax])
                nMax = j;

            Swap(nNumList[i], nNumList[nMax]);
        }
    }
}

// ================================================================
// IDENTIFIER:  MergeSort()
//
// PRE:         A list that needs to be sorted
//
// POST:        A list that is sorted
//
// CALLS:       MergeSort(int, int) -- Merge sort
//
// COMMENTS:    Sorts the array in ascending order using MergeSort
// ================================================================

void Sort::MergeSort()
{
    MergeSort(0, nTop);
}

// ================================================================
// IDENTIFIER:  QuickSort()
//
// PRE:         A list that needs to be sorted
//
// POST:        A list that is sorted
//
// CALLS:       QuickSort(int[], int, int)  -- Quick sort
//
// COMMENTS:    Sorts the array in ascending order using QuickSort
// ================================================================

void Sort::QuickSort()
{
    QuickSort(nNumList, 0, nTop);
}

// ================================================================
// IDENTIFIER:  HashSort()
//
// PRE:         A list that needs to be sorted
//
// POST:        A list that is sorted
//
// ALGORITHM:   Make a temporary list loaded with 0s. Increment
//              the elements of the temporary list by the
//              frequency of the numbers that appear in the first
//              list. Store the number back to the original list.
//
// EFFICIENCY   Best:       N^2
//              Average:    N^2
//              Worst:      N^2
//
// COMMENTS:    Sorts the array in ascending order using HashSort.
//              Bad overhead of using additional memory.
// ================================================================

void Sort::HashSort()
{
    int k = 0;
    int temp[MAX_NUM] = {0};

    for (int i = 0; i <= nTop; i++)
        temp[nNumList[i]]++;

    for (int j = 0; j < MAX_NUM; j++)
        for (int l = 0; l < temp[j]; l++)
            nNumList[k++] = j;
}

// ================================================================
// IDENTIFIER:  MergeSort(int, int)
//
// PRE:         A list that needs to be sorted
//
// POST:        A list that is sorted
//
// ALGORITHM:   If the first element is less than the last
//              element, find their midpoint and call itself
//              recursively twice with the first half then the
//              second half. After that, sort them and merge them
//              back into a single list. The splitting process has
//              an algorithm efficiency LogN, and the Merge process
//              is N. Thus, N*LogN.
//
// CALLS:       MergeSort(int, int) --  recursively call itself
//              MergeSort(int, int, int)    --  call Merge Sort
//
// EFFICIENCY   Best:       N*LogN
//              Average:    N*LogN
//              Worst:      N*LogN
//
// COMMENTS:    Sorts the array in ascending order using MergeSort.
// ================================================================

void Sort::MergeSort(int first, int last)
{
    if (first < last)
    {
        int mid = (first + last) / 2;

        MergeSort(first, mid);
        MergeSort(mid+1, last);
        MergeSort(first, mid, last);
    }
}

// ================================================================
// IDENTIFIER:  MergeSort(int, int, int)
//
// PRE:         A list that needs to be sorted
//
// POST:        A list that is sorted
//
// ALGORITHM:   N/A
//
// COMMENTS:    Sorts the array in ascending order using MergeSort.
//              Bad overhead of using additional memory.
// ================================================================

void Sort::MergeSort(int first, int mid, int last)
{
    int templist[MAX_NUM] = {0};
    int k1 = first;
    int k2 = mid + 1;
    int k3 = last;

    while (k1 <= mid && k2 <= last)
        if (nNumList[k1] < nNumList[k2])
            templist[k1++] = nNumList[k1];
        else
            templist[k1++] = nNumList[k2++];

    for (;k1 <= mid; )
    //while (k1 <= mid)
        templist[k1++] = nNumList[k1];

    for (; k2 <= last; )
        templist[k1++] = nNumList[k2++];

    for (k1 = first; k1 <= last; k1++)
        nNumList[k1] = templist[k1];
}

// ================================================================
// IDENTIFIER:  QuickSort(int[], int, int)
//
// PRE:         A list that needs to be sorted
//
// POST:        A list that is sorted
//
// ALGORITHM:   Chose a pivot in the middle of the list.
//              Place all numbers < pivot on the left.
//              Place all numbers > pivot on the right.
//              Sort each portion recursively.
//
// CALLS:       Swap(int&, int&)    --  calls swap routine
//              QuickSort(int[], int, int)
//                                  -- calls itself recursively
//
// EFFICIENCY   Best:       N*LogN
//              Average:    N*LogN
//              Worst:      N^2
//
// COMMENTS:    Sorts the array in ascending order using MergeSort.
// ================================================================

void Sort::QuickSort(int nNumList[], int first, int last)
{   
    if (last > first)
    {
        if ((last - first) >  3)
        {
            int pivot = (first + last) / 2;

            if (pivot != last)
                Swap(nNumList[pivot], nNumList[last]);
        }

        int i = first - 1;
        int j = last;

        while (1)
        {
            while (nNumList[++i] <  nNumList[last]);
            while (nNumList[--j] >  nNumList[last]);

            if (i >= j)
                break;
            else
                Swap(nNumList[i], nNumList[j]);
        }
        Swap(nNumList[i], nNumList[last]);
        QuickSort(nNumList, first, i-1);
        QuickSort(nNumList, i+1, last);
    }
}