//* sort generic algorithm complexity investigation *

#include <vector> #include <algorithm> #include <iostream> #include <ctime> #include <cstdlib> using namespace std; void Instruct(); void RandomizeVector(vector<double> &V); int main() { Instruct(); char ch; do { long int N; cout << "\aN= "; cin >> N; cout << "creating..." << endl; vector<double> V; V.resize(N); cout << "sorting..." << endl; time_t T1, T2; time( &T1 ); for (int i=1; i<1000; i++) { RandomizeVector(V); sort(V.begin(), V.end()); } time( &T2 ); long int TotalTime=T2-T1; if (TotalTime>100) { cout << "It took " << TotalTime << " ms. (+/- 1ms) to sort " << N << " numbers" << endl; } else { cout << "It took less than " << TotalTime << " ms. (+/- 1ms)." << endl << "That is not long enough to be accurate." << endl; } cout << "Do you want to run once again for different data size? "; cin >> ch; cin.ignore(256,'\n'); cout << "freeing memory..." << endl; } while (ch!='n'&&ch!='N'); return(0); } void RandomizeVector(vector<double> &V) { // look up the <ctime> in the compiler help time_t TimeInSeconds; time( &TimeInSeconds ); // initialize the pseudo random number generator srand((unsigned int)TimeInSeconds); // the value of the time in secs. is a OK way // to initialize the pseudo random number generator // rand() produces an integer number between 0-RAND_MAX for (int i=0; i<V.size(); i++) V[i]=double(rand())/double(RAND_MAX); } void Instruct() { cout << "\ This program evaluates the complexity of the generic algorithm for sorting\n\ \n\ Runles:\n\ 1. Run the program for large enough data set to measure time accurately.\n\ For reasonable accuracy each run should be longer than 100 (mili)seconds\n\ 2. Do not run any other programs when this program is running\n\ 2. Keep your program window in focus (top window).\n\ Otherwise it may run 50% slower (depending on your system setting)\n\ 3. During long runs prevent the screen saver from starting.\n\ \n\ \n\ Thank you." << endl << endl; }