Question

DIVIDE AND CONQUER

Implement the two algorithms for finding the kth smallest integer in a set of integers using only one array that contains all the integers. Test your programs and compute the CPU time for different sets of integers generated by a random number generator.

Must sure have the CPU time.

Answer 1

#include<iostream>
#include <cstdlib>
#include<time.h>
using namespace std;
void swap(int * a, int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}

int brootforce(int a[],int n,int k)
{
int i,j,min;
int size=n;
for(j=1;j<=k;j++,n--)
{
min=0;
for(i=1;i<n;i++)
{
if(a[min]>a[i])
{
min=i;
}
}
swap(&a[n-1],&a[min]);
}
return a[size-k];
}
int partition(int a[],int l,int r)
{
int i,j;
for(i=l,j=l;j<=r;j++)
{
if(a[j]<a[r])
{
swap(&a[i],&a[j]);
i++;
}
}
swap(&a[i],&a[r]);
return i;
}
int DAC(int a[],int l,int r,int k)
{
if(k>0 && k<=r-l+1)
{
int pivot=partition(a,l,r);
if(pivot-l==k-1)
return a[pivot];
if(pivot-l>k-1)
return DAC(a,l,pivot-1,k);
return DAC(a,pivot+1,r,k-pivot-1+l);
}
return -1;
}

int main()
{
int i=100;
int a[10000];
double time_taken;
clock_t t;
for(int i=0;i<10000;i++)
{
a[i]=i+1;
}
srand(time(0));
int r;
while(i--)
{
cout<<"Iteration: "<<i+1<<endl;
int max=10000;
for(int i=0;i<10000;i++,max--)
{
r=rand()%max;
swap(&a[r],&a[max-1]);
}
r=rand()%10000+1;
t = clock();
brootforce(a,10000,r);
t = clock() - t;
time_taken = ((double)t)/CLOCKS_PER_SEC;
cout<<"brootforce() took "<<time_taken<<"seconds\n";

t = clock();
DAC(a,0,9999,r);
t = clock() - t;
time_taken = ((double)t)/CLOCKS_PER_SEC;
cout<<"DAC() took "<<time_taken<<"seconds\n";
}
}

teration: 100
brootforce() took 0.137165seconds
DAC() took 0.000926seconds
Iteration: 99
brootforce() took 0.11362seconds
DAC() took 0.000716seconds
Iteration: 98
brootforce() took 0.058846seconds
DAC() took 0.000565seconds
Iteration: 97
brootforce() took 0.040972seconds
DAC() took 0.000329seconds
Iteration: 96
brootforce() took 0.040914seconds
DAC() took 0.000178seconds
Iteration: 95
brootforce() took 0.121494seconds
DAC() took 0.000888seconds
Iteration: 94
brootforce() took 0.069038seconds
DAC() took 0.00056seconds
Iteration: 93
brootforce() took 0.039016seconds
DAC() took 0.000195seconds
Iteration: 92
brootforce() took 0.068721seconds
DAC() took 0.000616seconds
Iteration: 91
brootforce() took 0.051939seconds
DAC() took 0.000416seconds
Iteration: 90
brootforce() took 0.131203seconds
DAC() took 0.000744seconds
Iteration: 89
brootforce() took 0.135701seconds
DAC() took 0.000521seconds
Iteration: 88
brootforce() took 0.090045seconds
DAC() took 0.000555seconds
Iteration: 87
brootforce() took 0.129142seconds
DAC() took 0.000768seconds
Iteration: 86
brootforce() took 0.128727seconds
DAC() took 0.001021seconds
Iteration: 85
brootforce() took 0.129583seconds
DAC() took 0.000815seconds
Iteration: 84
brootforce() took 0.083905seconds
DAC() took 0.000596seconds
Iteration: 83
brootforce() took 0.023002seconds
DAC() took 0.000523seconds
Iteration: 82
brootforce() took 0.031218seconds
DAC() took 0.000331seconds
Iteration: 81
brootforce() took 0.069087seconds
DAC() took 0.000494seconds
Iteration: 80
brootforce() took 0.101371seconds
DAC() took 0.00071seconds
Iteration: 79
brootforce() took 0.087531seconds
DAC() took 0.000544seconds
Iteration: 78
brootforce() took 0.108041seconds
DAC() took 0.000633seconds
Iteration: 77
brootforce() took 0.000266seconds
DAC() took 0.000198seconds
Iteration: 76
brootforce() took 0.030646seconds
DAC() took 0.000391seconds
Iteration: 75
brootforce() took 0.055807seconds
DAC() took 0.000622seconds
Iteration: 74
brootforce() took 0.129295seconds
DAC() took 0.000806seconds
Iteration: 73
brootforce() took 0.12317seconds
DAC() took 0.000726seconds
Iteration: 72
brootforce() took 0.058533seconds
DAC() took 0.000485seconds
Iteration: 71
brootforce() took 0.117206seconds
DAC() took 0.000869seconds
Iteration: 70
brootforce() took 0.048142seconds
DAC() took 0.000379seconds
Iteration: 69
brootforce() took 0.132389seconds
DAC() took 0.000847seconds
Iteration: 68
brootforce() took 0.127705seconds
DAC() took 0.000603seconds
Iteration: 67
brootforce() took 0.119727seconds
DAC() took 0.000573seconds
Iteration: 66
brootforce() took 0.004231seconds
DAC() took 0.000285seconds
Iteration: 65
brootforce() took 0.061037seconds
DAC() took 0.00041seconds
Iteration: 64
brootforce() took 0.095829seconds
DAC() took 0.000504seconds
Iteration: 63
brootforce() took 0.038883seconds
DAC() took 0.00041seconds
Iteration: 62
brootforce() took 0.033846seconds
DAC() took 0.00041seconds
Iteration: 61
brootforce() took 0.01941seconds
DAC() took 0.000222seconds
Iteration: 60
brootforce() took 0.131999seconds
DAC() took 0.000557seconds
Iteration: 59
brootforce() took 0.026399seconds
DAC() took 0.000184seconds
Iteration: 58
brootforce() took 0.042748seconds
DAC() took 0.000603seconds
Iteration: 57
brootforce() took 0.013628seconds
DAC() took 0.000292seconds
Iteration: 56
brootforce() took 0.131902seconds
DAC() took 0.000848seconds
Iteration: 55
brootforce() took 0.071388seconds
DAC() took 0.000274seconds
Iteration: 54
brootforce() took 0.074949seconds
DAC() took 0.000367seconds
Iteration: 53
brootforce() took 0.130213seconds
DAC() took 0.000957seconds
Iteration: 52
brootforce() took 0.133445seconds
DAC() took 0.000768seconds
Iteration: 51
brootforce() took 0.046403seconds
DAC() took 0.000533seconds
Iteration: 50
brootforce() took 0.068135seconds
DAC() took 0.000607seconds
Iteration: 49
brootforce() took 0.125371seconds
DAC() took 0.001031seconds
Iteration: 48
brootforce() took 0.112279seconds
DAC() took 0.000602seconds
Iteration: 47
brootforce() took 0.131578seconds
DAC() took 0.000377seconds
Iteration: 46
brootforce() took 0.070036seconds
DAC() took 0.000496seconds
Iteration: 45
brootforce() took 0.100934seconds
DAC() took 0.000651seconds
Iteration: 44
brootforce() took 0.125196seconds
DAC() took 0.001126seconds
Iteration: 43
brootforce() took 0.01428seconds
DAC() took 0.000394seconds
Iteration: 42
brootforce() took 0.113824seconds
DAC() took 0.000609seconds
Iteration: 41
brootforce() took 0.101546seconds
DAC() took 0.000714seconds
Iteration: 40
brootforce() took 0.00098seconds
DAC() took 0.000266seconds
Iteration: 39
brootforce() took 0.058767seconds
DAC() took 0.000431seconds
Iteration: 38
brootforce() took 0.09437seconds
DAC() took 0.000878seconds
Iteration: 37
brootforce() took 0.08223seconds
DAC() took 0.00047seconds
Iteration: 36
brootforce() took 0.111064seconds
DAC() took 0.000956seconds
Iteration: 35
brootforce() took 0.129108seconds
DAC() took 0.000778seconds
Iteration: 34
brootforce() took 0.133223seconds
DAC() took 0.000769seconds
Iteration: 33
brootforce() took 0.091501seconds
DAC() took 0.000689seconds
Iteration: 32
brootforce() took 0.117807seconds
DAC() took 0.000728seconds
Iteration: 31
brootforce() took 0.132821seconds
DAC() took 0.000581seconds
Iteration: 30
brootforce() took 0.138981seconds
DAC() took 0.00088seconds
Iteration: 29
brootforce() took 0.088637seconds
DAC() took 0.00077seconds
Iteration: 28
brootforce() took 0.041447seconds
DAC() took 0.000379seconds
Iteration: 27
brootforce() took 0.126821seconds
DAC() took 0.000598seconds
Iteration: 26
brootforce() took 0.110885seconds
DAC() took 0.000513seconds
Iteration: 25
brootforce() took 0.122493seconds
DAC() took 0.001145seconds
Iteration: 24
brootforce() took 0.117035seconds
DAC() took 0.000953seconds
Iteration: 23
brootforce() took 0.018786seconds
DAC() took 0.000186seconds
Iteration: 22
brootforce() took 0.000292seconds
DAC() took 0.000288seconds
Iteration: 21
brootforce() took 0.107934seconds
DAC() took 0.000963seconds
Iteration: 20
brootforce() took 0.114664seconds
DAC() took 0.000804seconds
Iteration: 19
brootforce() took 0.011936seconds
DAC() took 0.000131seconds
Iteration: 18
brootforce() took 0.000664seconds
DAC() took 0.000285seconds
Iteration: 17
brootforce() took 0.129946seconds
DAC() took 0.000629seconds
Iteration: 16
brootforce() took 0.037369seconds
DAC() took 0.000374seconds
Iteration: 15
brootforce() took 0.03226seconds
DAC() took 0.000383seconds
Iteration: 14
brootforce() took 0.037177seconds
DAC() took 0.000278seconds
Iteration: 13
brootforce() took 0.081285seconds
DAC() took 0.000508seconds
Iteration: 12
brootforce() took 0.098688seconds
DAC() took 0.0011seconds
Iteration: 11
brootforce() took 0.000134seconds
DAC() took 0.000388seconds
Iteration: 10
brootforce() took 0.126052seconds
DAC() took 0.000941seconds
Iteration: 9
brootforce() took 0.037972seconds
DAC() took 0.000452seconds
Iteration: 8
brootforce() took 0.085607seconds
DAC() took 0.000445seconds
Iteration: 7
brootforce() took 0.0409seconds
DAC() took 0.00027seconds
Iteration: 6
brootforce() took 0.121944seconds
DAC() took 0.000803seconds
Iteration: 5
brootforce() took 0.067007seconds
DAC() took 0.000558seconds
Iteration: 4
brootforce() took 0.108865seconds
DAC() took 0.000616seconds
Iteration: 3
brootforce() took 0.110891seconds
DAC() took 0.000658seconds
Iteration: 2
brootforce() took 0.033118seconds
DAC() took 0.000363seconds
Iteration: 1
brootforce() took 0.121802seconds
DAC() took 0.000654seconds