#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();*/ }