#include
using namespace std;

class SortAlgorithm
{
public:
    SortAlgorithm(int = 10);
    void displayVector();
    void swap(int &, int &);

    void insertSort();                     //O(n^2)
    void selectSort();                    //O(n^2)
    void mergeSort();                    //O(n log n)
    void bubbleSort();                  //O(n^2)
    void quickSort(  int , int  );     //worst: O(n^2),  best: O(n log n)

    int partition( int , int  );
    void sortSubVector(int , int );
    void merge(int , int , int , int );
private:
    int size;
    vector< int > source;
    vector< int > temp;

};

#include
#include // prototypes for functions srand and rand
#include // prototype for function time
#include // prototype for sort function
#include "SortAlgorithm.h" // class BinarySearch definition
using namespace std;

SortAlgorithm::SortAlgorithm(int vectorSize)
{
    size = ( vectorSize > 0 ? vectorSize : 10 ); // validate vectorSize
    srand( time( 0 ) ); // seed using current time

   // fill vector with random ints in range 10-99
    for ( int i = 0; i < size; i++ )
           source.push_back( 10 + rand() % 90 ); // 10-99

    temp = source;
}

void SortAlgorithm::insertSort()
{
    int insert;
    for(int next = 1; next < size; next++){
        insert = temp[next];
        int moveItem = next;

        while((moveItem > 0) && (temp[moveItem - 1] > insert)){
            temp[moveItem] = temp[moveItem - 1];
            moveItem--;
        }

        temp[moveItem] = insert;
    }
}

void SortAlgorithm::selectSort()
{
    int loop = size - 1;
    int smallest;

    for(int i = 0; i < loop; i++){
        smallest = i;

        for(int j = i + 1; j < size; j++){
            if(temp[j] < temp[smallest])
                smallest = j;
        }

        swap(temp[i], temp[smallest]);
    }
}

void SortAlgorithm::mergeSort()
{
    sortSubVector(0, size - 1);
}

void SortAlgorithm::bubbleSort()
{
       int comp; // used to control for loop and for subscripts
       bool swapCheck = true; // was a swap made?

    for ( int pass = 1; pass < size && swapCheck; pass++ ) {
        swapCheck = false; // assume no swaps will be made

      // traverse and compare unsorted part of vector
        for ( comp = 0; comp < size - pass; comp++ ){

         // compare adjacent vector elements
            if ( temp[ comp ] > temp[ comp + 1 ] ) {
                swap(temp[comp], temp[comp + 1]);
                swapCheck = true;
                 } // end if

        } // end inner for
    } // end outer for
}

void SortAlgorithm::quickSort(int first, int last )
{
   int currentLocation;

   if ( first >= last )
      return;

   currentLocation = partition( first, last ); // place an element
   quickSort( first, currentLocation - 1 ); // sort left side
   quickSort( currentLocation + 1, last ); // sort right side
} // end function quickSortHelper

// partition the vector into multiple sections
int SortAlgorithm::partition( int left, int right )
{
   int position = left;

   // loop through the portion of the vector
   while ( true )
   {
   //first: from right ro left
      while ( temp[ position ] temp[ right ])
      {
         swap( temp[ position ], temp[ right ] );
         position = right;
      } // end if
   //second: from left to right
      while ( temp[ left ] temp[ position ] )
      {
         swap( temp[ position ], temp[ left ] );
         position = left;
      } // end if
   } // end while
} // end function partition

void SortAlgorithm::sortSubVector(int low, int high)
{
    if((high - low) >= 1){
        int middle1 = (low + high) / 2;
        int middle2 = middle1 + 1;

        /*cout