Thread: I need help with this...

  1. #1
    Registered User
    Join Date
    Jun 2007

    Unhappy 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...
    #include <iostream>
    #include <vector>
    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];
        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] << "	";
    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...
      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++)
      int seed = static_cast<int> (time(0));
      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...
    #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 

  2. #2

Popular pages Recent additions subscribe to a feed