///////////////////////////////////////////////////////////////////////
//  SortStrategy.cpp - Strategy Example Code - Sorting               //
//  Ver: 1.1                                                         //
//  Language:   Visual C++ 2010                                      //
//  Platform:   Dell Dimension T7400, Win 7, Pro                     //
//  Author:     Jim Fawcett, CSE776 - Design Patterns, Fall 2011     //
//  Source:     Lei Zhang, lzhang17@syr.edu                          //
//              from internet - no longer have url                   //
///////////////////////////////////////////////////////////////////////

#include "SortStrategy.h"
#include <math.h>

void BubbleSort::sorting(std::vector<int> & num)
{
  for(size_t i=0; i<num.size(); ++i)
  {
    bool swapped = false;
    for(size_t j=0; j<num.size()-i-1; ++j)
    {
      if(num[j] > num[j+1])
      {
        int temp = num[j];
        num[j] = num[j+1];
        num[j+1] = temp;
        swapped = true;
      }
    }
    if (swapped == false)
      break;
  }
}

void InsertionSort::sorting(std::vector<int> & num)
{
  for(size_t j = 1; j < num.size(); ++j)
  {
    int key = num[j];
    int i = static_cast<int>(j - 1);
    while(i >= 0 && num[i] > key)
    {
      num[i + 1] = num[i];
      --i;
    }
    num[i + 1] = key;
  }
}

void QuickSort::sorting(std::vector<int> & num)
{
  Quick_Sort(num, 0, static_cast<int>(num.size()-1));
}

void QuickSort::Quick_Sort(std::vector<int> & num, int p, int r)
{
  if(p < r)
  {
    int q = partition(num, p, r);
    Quick_Sort(num, p, q - 1);
    Quick_Sort(num, q + 1, r);
  }
}

int QuickSort::partition(std::vector<int> & num, int p, int r)
{
  int x = num[r];
  int i = p - 1;
  for(int j = p; j < r; ++j)
  {
    if(num[j] <= x)
    {
      ++i;
      swap(num[i], num[j]);
    }
  }
  swap(num[i + 1], num[r]);
  return i + 1;
}

void QuickSort::swap(int & a, int & b)
{
  int temp = a;
  a = b;
  b = temp;
}


void MergeSort::sorting(std::vector<int> & num)
{
  Merge_Sort(num, 0, static_cast<int>(num.size()-1));
}

void MergeSort::Merge_Sort(std::vector<int> & num, int p, int r)
{
  if(p < r)
  {
    int q = static_cast<int>(floor(static_cast<float>((p + r)/2)));
    Merge_Sort(num, p, q);
    Merge_Sort(num, q + 1, r);
    Merge(num, p, q, r);
  }
}

void MergeSort::Merge(std::vector<int> & num, int p, int q, int r)
{
  int n1 = q - p + 1;
  int n2 = r - q;
  std::vector<int> L, R;
	
  for(int j = p; j <= q; ++j)
    L.push_back(num[j]);
  for(int j = q + 1; j <= r; ++j)
    R.push_back(num[j]);
  L.push_back(100000);
  R.push_back(100000);

  int i = 0;
  int j = 0;
  for(int k = p; k <= r; ++k)
  if(L[i] <= R[j])
  {
    num[k] = L[i];
    ++i;
  }
  else
  {
    num[k] = R[j];
    ++j;
  }
}