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
|
#include <iostream>
#include <time.h>
using namespace std;
void mergesort(int[], int, int);
void merge(int[], int, int, int);
void mergesort(int a[], int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
}
void merge(int a[], int low, int high, int mid)
{
int i, j, k, c[50];
i=low;
j=mid+1;
k=low;
while((i<=mid)&&(j<=high))
{
if(a[i]<a[j])
{
c[k]=a[i];
k++;
i++;
}
else
{
c[k]=a[j];
k++;
j++;
}
}
while(i<=mid)
{
c[k]=a[i];
k++;
i++;
}
while(j<=high)
{
c[k]=a[j];
k++;
j++;
}
for(i=low;i<k;i++)
{
a[i]=c[i];
}
}
int main ()
{
int randNum[100];
clock_t sTime;
srand((unsigned)clock());
cout << "Start generating random numbers..." << endl;
for(int index=0; index<100; index++){
randNum[index] = (rand()%1000)+1;
}
sTime = clock();
mergesort(randNum, 0, 99);
// delay the program by 0.05 second
clock_t cWait = clock();
cout << "Total CPU time used: " << (double) (clock()-sTime)/CLOCKS_PER_SEC \
<< " seconds" << endl;
}
|