#include <vector>
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 <iostream>
#include <cstdlib> // prototypes for functions srand and rand
#include <ctime> // prototype for function time
#include <algorithm> // 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 ] && position != right )
???????? --right;

????? if ( position == right )
???????? return position;

????? if ( temp[ position ] > temp[ right ])
????? {
???????? swap( temp[ position ], temp[ right ] );
???????? position = right;
????? } // end if
?? //second: from left to right
????? while ( temp[ left ] <= temp[ position ] && left != position )
???????? ++left;

????? if ( position == left )
???????? return position;

????? if ( 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 << "split:?? ";
??????? displaySubVector(low, high);
??????? cout << endl << "?????? ";
??????? displaySubVector(low, middle1);
??????? cout << endl << "?????? ";
??????? displaySubVector(middle2, high);
??????? cout << endl << endl;*/

??????? sortSubVector(low, middle1);
??????? //cout << "Stop here1. low = " << low << ", middle1 = " << middle1 << endl;
??????? sortSubVector(middle2, high);
??????? //cout << "Stop here2. middle2 = " << middle2 << ", high = " << high << endl;

??????? merge(low, middle1, middle2, high);

??? }
}

void SortAlgorithm::merge(int left, int middle1, int middle2, int right)
{
??? int leftIndex = left;
??? int rightIndex = middle2;
??? int combinedIndex = left;
??? vector<int> combined(size);

??? /*cout << "merge:?? ";
??? displaySubVector(left, middle1);
??? cout << endl << "?????? ";
??? displaySubVector(middle2, right);
??? cout << endl;*/

??? while(leftIndex <= middle1 && rightIndex <= right){
??????? if(temp[leftIndex] <= temp[rightIndex])
??????????? combined[combinedIndex++] = temp[leftIndex++];
??????? else
??????????? combined[combinedIndex++] = temp[rightIndex++];
??? }

??? if(leftIndex == middle2){
??????? while(rightIndex <= right)
??????????? combined[combinedIndex++] = temp[rightIndex++];
??? }
??? else{
??????? while(leftIndex <= middle1)
??????????? combined[combinedIndex++] = temp[leftIndex++];
??? }

??? for(int i = left; i <= right; i++)
??????? temp[i] = combined[i];

??? /*cout << "?????? ";
??? displaySubVector(left, right);
??? cout << endl << endl;*/
}

void SortAlgorithm::swap(int &x, int &y)
{
??? int t;

??? t = x;
??? x = y;
??? y = t;
}

void SortAlgorithm::displayVector()
{
??? for(int i = 0; i < size; i++){
??????? cout << " " << temp[i];
??????? if((i + 1) % 10 == 0)
??????????? cout << endl;
??? }

??? cout << endl;

??? temp = source;
}

#include <iostream>
#include "SortAlgorithm.h" // class BinarySearch definition
#include "BucketSort.h"
using namespace std;

?

int main()
{
??? int num;
??? cout << "Please input the integer number you want to sort:? ";
??? cin >> num;

??? SortAlgorithm sortVector(num);
??? cout << "Unsort elements: /n";
??? sortVector.displayVector();

??? sortVector.insertSort();
??? cout << "/nInsert sorted elements: /n";
??? sortVector.displayVector();

??? sortVector.selectSort();
??? cout << "/nSelect sorted elements: /n";
??? sortVector.displayVector();

??? sortVector.mergeSort();
??? cout << "/nMerge sorted elements: /n";
??? sortVector.displayVector();

??? sortVector.bubbleSort();
??? cout << "/nBubble sorted elements: /n";
??? sortVector.displayVector();

??? sortVector.quickSort(0, num - 1);
??? cout << "/nQuick sorted elements: /n";
??? sortVector.displayVector();

?? /*BucketSort bucketSortVector( num ); // create BucketSort object

?? cout << "Vector elements in original order:/n";
?? bucketSortVector.displayElements();

?? bucketSortVector.sort(); // sort the vector

?? cout << "/nVector elements in sorted order:/n";
?? bucketSortVector.displayElements();*/
}