/* SortLibrary contains various sorting algorithms
 *
 * Written by:   Larry R. Nyhoff
 * Written for:  Lab Manual for C++: An Introduction to Data Structures
 *
 * Add other documentation required by your instructor such as your name, 
 * course number, and the current date.
 *************************************************************************/

#include <string>
#include <vector>
using namespace std;


// Swap utility
//   Receive:   Type parameter ElementType
//              a and b of type ElementType
//   Pass back: a and b with values interchanged
//--------------------------------------------------
template <typename ElementType>
void Swap(ElementType & a, ElementType & b)
{
  ElementType temp = a;
  a = b;
  b = temp;
}


// BUBBLE SORT -- first version
//   Receive:   Type parameter ElementType
//              vector x with elements of type ElementType
//   Pass back: x sorted in ascending order
//---------------------------------------------------------

template <class ElementType>
void BubbleSort(vector<ElementType> & x)
{
  for (int listSize = x.size() - 1; listSize > 1; listSize--)
    for (int j = 1; j < listSize; j++)
      if (x[j] > x[j+1])
        Swap(x[j], x[j+1]);
}


/* SECOND VERSION OF BUBBLE SORT BEGINS HERE

// BUBBLE SORT -- improved version
//   Receive:   Type parameter ElementType
//              vector x with elements of type ElementType
//   Pass back: x sorted in ascending order
//---------------------------------------------------------

template <class ElementType>
void BubbleSort(vector<ElementType> & x)
{
  int numPairs = x.size() - 2;
  for(;;)
  {
    if (numPairs == 0) return;

    int last = 1;
    for (int i = 1; i <= numPairs; i++)
      if (x[i] > x[i+1])
      {
        Swap(x[i], x[i+1]);
        last = i;
      }
    numPairs = last - 1;
  }
}

*** SECOND VERSION OF BUBBLE SORT ENDS HERE ***/



// Split rearranges x[first], ... , x[last] so that
// the pivot element is properly positioned at
// position pos.
//   Receive:   Type parameter ElementType
//              vector x, indices first, last
//   Pass back: Rearranged x, index pos
//---------------------------------------------------------

template <class ElementType>

void Split(vector<ElementType> & x,
           int first, int last, int & pos)
{
  ElementType pivot = x[first]; // pivot element
  int left = first,             // index for left search
      right = last;             // index for right search

  while (left < right)
  {
    // Search from right for element <= pivot
    while (x[right] > pivot)
      right--;
    // Search from left for element > pivot
    while (left < right && x[left] <= pivot)
      left++;
    // Interchange elements if searches haven't met
    if (left < right)
      Swap(x[left], x[right]);
  }
  // End of searches; place pivot in correct position
  pos = right;
  x[first] = x[pos];
  x[pos] = pivot;
}


// QUICKSORT
//   Receive:   Type parameter ElementType
//              vector x with elements of type ElementType
//              indices first and last
//   Pass back: Rearranged x with x[first], ..., x[last]
//                in ascending order
//---------------------------------------------------------

template <class ElementType>

void Quicksort(vector<ElementType> & x, int first, int last)
{
  int pos;          // final position of pivot
  if (first < last) // list has more than one element
  {
    // Split into two sublists
    Split(x, first, last, pos);
    // Sort left sublist
    Quicksort(x, first, pos - 1);
    // Sort right sublist
    Quicksort(x, pos + 1, last);
  }
  // else list has 0 or 1 element and
  // requires no sorting
}

// Function template interface to QuickSort()
//   Receive:   Type parameter ElementType
//              vector x with elements of type ElementType
//   Pass back: x sorted in ascending order.
//---------------------------------------------------------

template <typename ElementType>

void QSort(vector<ElementType> & x)
{
  Quicksort(x, 1, x.size() - 1);
}