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...
Code:
#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
}
Thankz