How to I get this program to show something other than zeros for the time when I

Question

How to I get this program to show something other than zeros for the time when I run it

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

void selectionSort(int array[], int n)
{
   int i, j, index;

   // One by one move boundary of unsorted subarray
   for (i = 0; i < n - 1; i++)
   {
       // Find the minimum element in unsorted array
       index = i;
       for (j = i + 1; j < n; j++)
       if (array[j] < array[index])
           index = j;

       // Swap the found minimum element with the first element
       int temp = array[index];
       array[index] = array[i];
       array[i] = temp;
   }
}

// Linearly search x in array[]. If x is present then return its
// location, otherwise return -1
int linearSearch(int array[], int n, int x)
{
   int i;
   for (i = 0; i<n; i++)
   if (array[i] == x)
       return i;
   return -1;
}

// A iterative binary search function. It returns location of x in
// given array array[l..r] if present, otherwise -1
int binarySearch(int array[], int n, int x)
{
   int l = 0, r = n - 1;
   while (l <= r)
   {
       int m = l + (r - l) / 2;

       // Check if x is present at mid
       if (array[m] == x)
           return m;

       // If x greater, ignore left half
       if (array[m] < x)
           l = m + 1;

       // If x is smaller, ignore right half
       else
           r = m - 1;
   }

   // if we reach here, then element was not present
   return -1;
}

int main(void)
{
   int array[1000];
   srand(time(0));

   for (int i = 0; i<1000; i++)
       array[i] = rand() % 100 + 1;

   clock_t t;
   t = clock();

   linearSearch(array, 1000, 77);

   t = clock() - t;

   double timeTaken = ((double)t) / CLOCKS_PER_SEC; // in seconds
   cout << "Time taken by linear search: " << timeTaken << endl;

   selectionSort(array, 1000);

   t = clock();

   binarySearch(array, 1000, 77);

   t = clock() - t;
   timeTaken = ((double)t) / CLOCKS_PER_SEC; // in seconds
   cout << "Time taken by binary search: " << timeTaken << endl;
   system("pause");
   return 0;
}

Explanation / Answer

Solution:

when we run the program we might get different results because we are using array of 1000 elements and those are arranged in random order so to search the given key i.e., 77 we have three different cases so in the best case the key might be the 1st element in the array then it return minimum time sometimes it might return 0 and in the average case key might be the middle element then the average time we get and in the worst case the key might not in the array or it might be the last element of array then we get large times.

based on several runs of the program I get the following different outpus.

Sample Output1:

Time taken by linear search: 1e-06   
Time taken by binary search: 2e-06

Sample Output2:

Time taken by linear search: 1e-06   
Time taken by binary search: 0

Sample Output3:

Time taken by linear search: 2e-06   
Time taken by binary search: 1e-06

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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