Part 1: sort with vectors

Write functions implementing an insertion sort. The function input is a list of integers (passed by reference), and an integer N which is the number of items in the list. The function should return an integer W which counts the number of comparison operations + the number of writes to the list, which we will take as a measure of the amount of work performed.

Your list of integers should be stored as a C++ vector.

Your program should include 3 functions: main() ; and one function per sorting algorithm above. main() generates 3 sets of N integers. The first set should consist of an increasing sequence of numbers. The third set should be a random sequence The second set should consist of a decreasing sequence of numbers. The third set should consist of random numbers. Each set of N integers should be submitted to both sort algorithms. Measure the time it takes for each algorithm and each set of integers (type 'man clock' at the linux prompt for a description of the clock function).

For each function call, output one line, with the following information:

N, sort-type, data-set, W, time

Where sort tipe = {select, insert}; data set {increasing, deccreasing, random}.

Use the following values for N:

5000, 10000, 15000, 20000

Part 2: sort with arrays

Modify the above program to use a C-style array instead of a vector as the data structure that holds your list, and run it again.

Part 3: analysis

What can you conclude from your output? Specifically: is either algorithm better? Is either data structure superior? Do the algorithms scale with N as you expect?

////////////////// I was thinking of using a template for this with some minor moddz...

if anyone has an idea for this, please post^^

//here is the template...

Code:#include <iostream> #include <vector> #include<math.h> #include<time.h> using namespace std; template <class T>//insertion sort int sort( vector <T> &a) { for(int i = 1; i < a.size(); i++) { T ele = a[i]; int j = i - 1; while ( j >= 0 && ele > a[j]) { a[j+1] = a[j]; j--; } a[j+1] = ele; } } template <class T>//print vector void print(vector <T> &a) { for(int i = 0; i <a.size(); i++) { cout << a[i] << " "; } return; } unsigned int getRandom(int n)//generate random integer { unsigned int r = rand(); return r % n; } int main() { cout << "sorting insertion.cpp" << endl;//sort integer static char buffer[100]; vector <string> vs; //FILE *fp; // if(( fp = fopen( "insertion.cpp", "rt")) == NULL) //{ // cout << "Error opening file insertion.cpp" << endl; // return 1; // } // while( fscanf( fp, "%s", buffer) != EOF) // { // vs.push_back( string(buffer)); // } Thinking of changing this part... sort(vs); print(vs); cout << endl; int n; cout << "how many numbers do you want to sort: "; cin >> n; vector <int> num; for(int i = 0; i < n; i++) { num.push_back(getRandom(n)); } int seed = static_cast<int> (time(0)); srand(seed); time_t time_before, time_after; time_before = time((time_t *) 0 ); sort(num);//sort integers time_after = time((time_t * ) 0 ); cout << "time to sort is " << time_after - time_before << " seconds" << endl; cout << endl; return 0; }

Here is the timming function i will use...

ThankzCode:#include <iostream> #include <iomanip> #include <ctime> using namespace std; int main() { long i,j; double c; c = clock(); // initialize clock value for(i=0;i<1e8;i++){ j = i; } // dummy delay loop c = clock()-c; //get time difference cout << clock() << endl; // output difference - ticks cout << c/CLOCKS_PER_SEC << endl; // output difference - seconds // takes .5 seconds on 2GHz P4 }