C++

Forum

 
Calculating Time complexity of a couple functions

parmih4 (10)
Hi everyone!
I just started the topic of time complexity and the usage of clock_t. Now let's say I want to calculate how long it takes for the compiler to calculate:
1. binary search
2. quick sort
3. linear search
4. bubble sort
5. Hanoi
I've written bubble sort, binary search and quick sort and haven't finished with linear and Hanoi. I was wondering if you would look at my code and see if things are okay
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
 #include <iostream>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <windows.h>
using namespace std;

int bin_search(int [], int, int);	//Function: LogN//
void quick_sort(int[], int , int);	//Function: NLogN//
void bubble_sort(int[], int);		//Function: N^2//
void linearSearch(int data[], int length, int val); //Function:N^2//

void fill_array(int[], int);
void display_array(int[], int);

int main()
{
const int size1=1000;
int A[size1];
clock_t start_time, end_time;

fill_array(A,size1);
bubble_sort(A,size1);

start_time=clock();
bubble_sort(A,size1);
quick_sort(A,0, size1-1);
bin_search(A,size1, -2);
end_time=clock();
cout << "Time= " << (end_time - start_time) << endl;

system("pause");
}

int bin_search(int A[], int n, int key)
{
int low, high, mid;
clock_t start_time, end_time;
start_time=clock();
low=0;
high=n-1;
while(low< high)
{
 mid = (low+high)/2;
 if (A[mid]==key)
       return mid;
 else if (A[mid]<key)
 	   low=mid+1;
 else
      high=mid-1;

Sleep(20);
end_time=clock();
}

cout<<"Time="<<(end_time - start_time)<<endl;
   return -1;

}




void quick_sort(int A[], int left, int right)
{
int pivot, i, j, temp;

i=left;
j=right+1;
pivot=A[left];

if(left< right)
{
do
{
   do
   {
    i++;
   }
   while(A[i]<pivot);

   do
   {
    j--;
   }
   while(A[j]>pivot);
   if(i<j)
   {
    temp=A[i];
    A[i]=A[j];
    A[j]=temp;
   }

} while (i<j); 
  temp=A[j];
  A[j]=A[left];
  A[left]=temp;

  Sleep(1);
  quick_sort(A,left, j-1);
  quick_sort(A,j+1, right);
 }
}


void bubble_sort(int A[], int n)
{
int i, pass, flag, temp;
clock_t start_time, end_time;

start_time=clock();
flag=0;
pass=1;
while (flag==1 || pass <=n)
{
 flag=0;
 for(i=0;i<=n-pass; i++)
 {
   if (A[i] > A[i+1])
      {
       temp=A[i];
       A[i]=A[i+1];
       A[i+1]=temp;
       flag=1;
       }
   }
   pass++;
}
end_time=clock();
cout<<"Time="<<(end_time - start_time)<<endl;


}


void display_array(int A[], int n)
{
 int i;

for(i=0;i<n ; i++)
{

 cout << A[i] << endl;
}

}

void fill_array(int A[], int n)
{
int i;

for(i=0;i<n ; i++)
{

 A[i]=rand()% 1000+1;
}
}
ne555 (10692)
- learn to indent
- ¿why `Sleep()'?
- ¿who's timing `quicksort()'?
- linear search is O(n)
- out of bounds in `bubblesort()'
Last edited on
Nick Schuck (12)
I am not entirely sure, but depending on what system you ran this on you might get an incorrect answer with this code. If its a multi-threaded system, and your process is stopped to allow another process to run, that time that another process is running would be added into the total time of your process.
Topic archived. No new replies allowed.