Project for algorithm analysis Generate 100000 positive numbers between (0, 150)

Question

Project for algorithm analysis Generate 100000 positive numbers between (0, 150) Search the position of the first "58" in the array Count how many "58" in the array Sort the array Repeat step 3 on the sorted array and compute the time cost difference between the time from step 3 only, and time from step 4 and 5 together. Run your program three times and calculate the time: The time to generate 100000# The time to search the element 58 (step 2) The time to count the 58's (step 3) The time to sort the array (step 4) Step 5 (difference of 4 5 and step 3)

Explanation / Answer

#include <iostream>
#include <bits/stdc++.h>
#include <time.h>
#include <sys/time.h>
#include <stdlib.h>
typedef unsigned long long timestamp_t;

using namespace std;

static timestamp_t
get_timestamp ()
{
struct timeval now;
gettimeofday (&now, NULL);
return now.tv_usec + (timestamp_t)now.tv_sec * 1000000;
}

int main(){
   int num = 0;
   timestamp_t t0,t1,t2,t3,t4,t5;
   int num1=0;
   t0 = get_timestamp();
   clock_t startTime = clock();
   int a[100000];
   for (int i =0 ; i < 100000 ; i++){
       a[i] = rand() % 150 +1;
       //cout << a[i] << endl;
   }
   t1 = get_timestamp();
   for (int i = 0 ; i < 100000 ; i++){
       if(a[i] == 58){
           num = num +1;
           if (num == 1){
               cout << "58 found in " << i << endl;
               t2 = get_timestamp();  
           }
       }
   }
   t3 = get_timestamp();
   cout << "number of 58 in un-sorted array= " << num << endl;
   sort(a, a + 100000);
   t4 = get_timestamp();
   for (int i =0; i < 100000 ; i++){
      
       if (a[i]==58){
           num1 = num1+1;
           }
       else if (a[i] > 58){
           cout << "number of 58 in sorted array " << num1 <<endl;
           break;
           }
       }
   t5 = get_timestamp();
   double secs = (t2 - t0) / 1000000.0L;
   cout << "time to generate 10000# = " << (t1 - t0) / 1000000.0L << "secs"<<endl;
   cout << "time to search the element 58 = "<< (t2 - t1) / 1000000.0L << "secs"<<endl;
   cout << "time to count the 58 = "<< (t3 - t2) / 1000000.0L << "secs"<<endl;
   cout << "time to sort the array = "<< (t4 - t3) / 1000000.0L << "secs" <<endl;
   cout << "time in step 5 = "<< (t5 - t4) / 1000000.0L << "secs" <<endl;
}

/*
First time :
   time to generate 10000# = 0.004351secs
   time to search the element 58 = 0.0001secs
   time to count the 58 = 0.000904secs
   time to sort the array = 0.03016secs
   time in step 5 = 0.000211secs

Second time :
   time to generate 10000# = 0.001492secs
   time to search the element 58 = 2.9e-05secs
   time to count the 58 = 0.000296secs
   time to sort the array = 0.014592secs
   time in step 5 = 0.000129secs

Third time :
   time to generate 10000# = 0.002478secs
   time to search the element 58 = 4.1e-05secs
   time to count the 58 = 0.000516secs
   time to sort the array = 0.019306secs
   time in step 5 = 0.000127secs

*/

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.