I need help with this...

This is a discussion on I need help with this... within the C++ Programming forums, part of the General Programming Boards category; Part 1: sort with vectors Write functions implementing an insertion sort. The function input is a list of integers (passed ...

  1. #1
    Registered User
    Join Date
    Jun 2007
    Posts
    4

    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...
    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

  2. #2
    Registered User
    Join Date
    May 2006
    Posts
    903
    And your question is ?

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21