static counter for comparisons
Hey guys, i wanted to the performance in terms of comparisons of this algorithm from http://www.inf.fh-flensburg.de/lang/...e/natmerge.htm
against my other bottom-up mergesort program.
I implemented a static int that's pass from main to the functions.
But the result is always 0.... why?
Here's my translation of C++ to C:
Code:
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
void sort(int array[],int size, int comp);
static bool mergeruns(int a[], int b[], int n, int comp);
void merge(int a[], int b[], int lo, int hi, bool asc, int comp);
void naturalmergesort(int a[], int b[], int n, int comp);
int main(int argc, char **argv)
{
int array[50];
int item,j, i=0;
static int comp=0;
while(scanf("%d", &item) > 0)
{
array[i] = item;
i++;
}
sort(array,i,comp);
for(j=0; j < i; j++)
printf("%d ", array[j]);
printf("\n");
printf("%d comparisons made\n", comp);
return 0;
}
void sort(int array[],int size, int comp)
{
int b[50];
int n=size;
naturalmergesort(array, b, n, comp);
}
static bool mergeruns(int a[], int b[], int n, int comp)
{
int i=0, k=0, x;
bool asc=true;
while (i<n)
{
k=i;
do x=a[i++]; while (i<n && x<=a[i]);
while (i<n && x>=a[i]) x=a[i++];
merge (a, b, k, i-1, asc, comp);
asc=!asc;
}
return k==0;
}
void merge(int a[], int b[], int lo, int hi, bool asc, int comp)
{
int l = lo; int r = hi;
int k=asc ? l : r;
int c=asc ? 1 : -1;
int i=lo, j=hi;
while (i<=j)
{
if (a[i]<=a[j])
{
b[k]=a[i++];
comp++;
}
else
{
b[k]=a[j--];
comp++;
}
k+=c;
}
}
void naturalmergesort(int a[], int b[], int n, int comp)
{
while (!mergeruns(a, b, n, comp) & !mergeruns(b, a, n, comp));
}
pointer help! & clock timing units
Hi guys,
I actually need to also count the comparisons, but I thank you for the timing suggestion too , of which i will be using and is of great help.
However, what units will the result be for the time difference of clock()? My result is always 0.0000 .... I'm running it on Mandrake 10.1....
It's under >> man clock? ...because they said, clock ticks are miliseconds.
And apart from that, can i get a lil help on pointers again? My comparison pointer keeps on printing 0....
Here's what i did..
Code:
int main(int argc, char **argv)
{
int array[50];
int item,j, i=0;
int *comp = malloc(sizeof(int));
int comp_result;
clock_t start, stop;
double t;
while(scanf("%d", &item) > 0)
{
array[i] = item;
i++;
}
start = clock();
sort(array,i,comp);
stop = clock();
t = (double)(stop-start);
comp_result = *comp;
for(j=0; j < i; j++)
printf("%d ", array[j]);
printf("\n");
printf("%d comparisons made\n", comp_result);
printf("Time taken : %.10lf\n", t);
return 0;
}
void sort(int array[],int size, int *comp)
{
int b[50];
int n=size;
naturalmergesort(array, b, n, comp);
}
static bool mergeruns(int a[], int b[], int n, int *comp)
{
int i=0, k=0, x;
bool asc=true;
while (i<n)
{
k=i;
do x=a[i++]; while (i<n && x<=a[i]);
while (i<n && x>=a[i]) x=a[i++];
merge (a, b, k, i-1, asc, comp);
asc=!asc;
}
return k==0;
}
void merge(int a[], int b[], int lo, int hi, bool asc, int *comp)
{
int l = lo; int r = hi;
int k=asc ? l : r;
int c=asc ? 1 : -1;
int i=lo, j=hi;
int comparisons = 0;
while (i<=j)
{
if (a[i]<=a[j])
{
b[k]=a[i++];
comparisons++;
}
else
{
b[k]=a[j--];
comparisons++;
}
k+=c;
}
comp = &comparisons;
}
void naturalmergesort(int a[], int b[], int n, int *comp)
{
while (!mergeruns(a, b, n, comp) & !mergeruns(b, a, n, comp));
}