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

}