By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,275 Members | 920 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,275 IT Pros & Developers. It's quick & easy.

merge sort #of comparisons

P: n/a
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
fr**********@msn.com
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[i]=temp[i];
delete [] temp;
}
Jul 22 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
Kevin King wrote:
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

--
"As a scientist, Throckmorton knew that if he were ever to break wind in
the echo chamber, he would never hear the end of it."

Jul 22 '05 #2

P: n/a
fr**********@msn.com (Kevin King) wrote in message news:<fb**************************@posting.google. com>...
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
fr**********@msn.com
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[i]=temp[i];
delete [] temp;
}

Jul 22 '05 #3

P: n/a

"Kevin King" <fr**********@msn.com> wrote in message
news:fb**************************@posting.google.c om...
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
fr**********@msn.com
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[i]=temp[i];
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
Jul 22 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.