Thread: I need help with this...

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