merge sort #of comparisons

K

Kevin King

I have a question about an assignment I have. I need to count the
number of comparisons in my merge sort. I know that the function is
roughly nlog(n), but I am definately coming up with too many
comparisons. It seems to me like I should just use a single counter in
the merge function's 'if' statement, but this can't be right because
an array of 50 takes about 100 comparisons this way. If anyone has any
suggestions I would greatly appreciate it.
-Kevin
(e-mail address removed)


void mergeSort(int data[], int size)
{
int n1,n2;

if(size>1)
{
n1=size/2;
n2=size-n1;
mergeSort(data,n1);
mergeSort((data+n1),n2);

merge(data, n1,n2);
}

}


void merge(int data[], int n1, int n2)
{
int *temp;
int copied=0;
int copied1=0;
int copied2=0;
int i;
temp=new int[n1+n2];
while((copied1<n1) &&(copied2<n2))
{
if(data[copied1]<(data+n1)[copied2])
temp[copied++]=data[copied1++];
else
temp[copied++]=(data+n1)[copied2++];
}
while(copied1<n1)
temp[copied++]=data[copied1++];
while(copied2<n2)
temp[copied++]=(data+n1)[copied2++];
for(i=0;i<n1+n2;i++)
data=temp;
delete [] temp;
}
 
D

David Rubin

Kevin said:
I have a question about an assignment I have. I need to count the
number of comparisons in my merge sort. I know that the function is
roughly nlog(n), but I am definately coming up with too many
comparisons. It seems to me like I should just use a single counter in
the merge function's 'if' statement, but this can't be right because
an array of 50 takes about 100 comparisons this way. If anyone has any
suggestions I would greatly appreciate it.

Big O notation expresses the asymptotic average case 'performance'. It's
not exact. Often times there are constant factors and additional work
that has to be done depending on the algorithm, the implementation, and
the input. Your function may require a very large domain and/or many
different input sets before you see n log n performance.

One thing which might be affecting your program directly is the
randomness of your input and the number of different executions you are
averaging over.

/david
 
E

Evan

I have a question about an assignment I have. I need to count the
number of comparisons in my merge sort. I know that the function is
roughly nlog(n), but I am definately coming up with too many
comparisons. It seems to me like I should just use a single counter in
the merge function's 'if' statement, but this can't be right because
an array of 50 takes about 100 comparisons this way. If anyone has any
suggestions I would greatly appreciate it.
-Kevin
(e-mail address removed)

As David already pointed out, Merge sort is "merely" order n log n.
The number of comparisons could be closer to, say, 10nlog(n). It could
even take 1000000*n*log(n) comparisons and still be of this order.

Big-O notation tells more about changes in running time if you change
the input rather than absolute time. For instance, if you double the
input size of radix sort (which sorts in O(n) time), you will
approximately double the output size. If you double the input size to
bubble sort (order n^2), you will approximately quadruple the output
time. If you double the input size to Merge Sort, you'll increase the
running time by about 160% (so it will take 2.6 times as long). Note
that the larger the input size was to begin with, the closer actual
measurements will be to these "ideal" values.

Evan

void mergeSort(int data[], int size)
{
int n1,n2;

if(size>1)
{
n1=size/2;
n2=size-n1;
mergeSort(data,n1);
mergeSort((data+n1),n2);

merge(data, n1,n2);
}

}


void merge(int data[], int n1, int n2)
{
int *temp;
int copied=0;
int copied1=0;
int copied2=0;
int i;
temp=new int[n1+n2];
while((copied1<n1) &&(copied2<n2))
{
if(data[copied1]<(data+n1)[copied2])
temp[copied++]=data[copied1++];
else
temp[copied++]=(data+n1)[copied2++];
}
while(copied1<n1)
temp[copied++]=data[copied1++];
while(copied2<n2)
temp[copied++]=(data+n1)[copied2++];
for(i=0;i<n1+n2;i++)
data=temp;
delete [] temp;
}
 
E

Elie Nader

Kevin King said:
I have a question about an assignment I have. I need to count the
number of comparisons in my merge sort. I know that the function is
roughly nlog(n), but I am definately coming up with too many
comparisons. It seems to me like I should just use a single counter in
the merge function's 'if' statement, but this can't be right because
an array of 50 takes about 100 comparisons this way. If anyone has any
suggestions I would greatly appreciate it.
-Kevin
(e-mail address removed)


void mergeSort(int data[], int size)
{
int n1,n2;

if(size>1)
{
n1=size/2;
n2=size-n1;
mergeSort(data,n1);
mergeSort((data+n1),n2);

merge(data, n1,n2);
}

}


void merge(int data[], int n1, int n2)
{
int *temp;
int copied=0;
int copied1=0;
int copied2=0;
int i;
temp=new int[n1+n2];
while((copied1<n1) &&(copied2<n2))
{
if(data[copied1]<(data+n1)[copied2])
temp[copied++]=data[copied1++];
else
temp[copied++]=(data+n1)[copied2++];
}
while(copied1<n1)
temp[copied++]=data[copied1++];
while(copied2<n2)
temp[copied++]=(data+n1)[copied2++];
for(i=0;i<n1+n2;i++)
data=temp;
delete [] temp;
}


honestly, I didn't read your code.
but I had the same problem in my assignment, and I figure out that I was
counting all the comparisons.
you have to differentiate, in "merge sort", the DATA comparison and the
INDEX comparison.
index comparisons should not be counted as comparisons.
note also that the numner of moves is always the same whatever is the size
of your array.
coz, when sorting, you copy your whole array to a 'temp' array, and then you
re-copy it, in different order by comparing the indexes(not counted) and
comparing the Data in the array(counted).
i hope that would would help you....
in case you want the implemantation of merge sort (Shaffer Code), i have
ready and modified in a way that counts the number os moves and comparisons.

Eliaho_O
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top