#include #include #include using namespace std; #include "ctimer.h" #include "sortall.h" #include "randgen.h" #include "prompt.h" // compare running times of quadratic sorts void PrepareVector(vector & a, int count, int mode) // precondition: a has space for count elements // postcondition: a contains 0..count-1 randomly shuffled if mode is 1 // a is created as ordered if mode 2 // a is in reverse order if mode is 3 { RandGen gen; // for random # generator int randIndex, k; // fill with valuesl 0..count-1 if (mode != 3) { for (k=0; k < count; k++) { a[k] = k; } } else { for(k=0; k < count; k++) { a[k] = count - 1 - k; } } // choose random index from k..count-1 and interchange with k if (mode == 1) { for (k=0; k < count - 1; k++) { randIndex = gen.RandInt(k, count-1); // random index Swap(a, k, randIndex); // swap in sortall.h } } } int main() { int size, minSize, maxSize, incr; // sort minSize, minSize+incr, ... maxSize CTimer timer; cout << "min and max size of vector: "; cin >> minSize >> maxSize; incr = PromptRange("increment in vector size",1,1000); cout << endl; for (int mode=1; mode <= 3; mode++) { if (mode == 1) cout << "Random vector" << endl; else if (mode == 2) cout << "Ordered vector" << endl; else if (mode == 3) cout << "Reverse ordered vector" << endl; cout << "n\tinsert\tselect" << endl; for (size=minSize; size <= maxSize; size += incr) { vector copy(size), original(size); cout << size << "\t"; PrepareVector(original,size, mode); copy = original; // sort using insertion sort timer.Start(); InsertSort(copy,copy.size()); timer.Stop(); cout << timer.ElapsedTime() << "\t"; copy = original; // sort using selection sort timer.Start(); SelectSort(copy,copy.size()); timer.Stop(); cout << timer.ElapsedTime() << "\t\n"; } cout <<"\n\n"; } return 0; }