Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > merge sort #of comparisons

Reply
Thread Tools

merge sort #of comparisons

 
 
Kevin King
Guest
Posts: n/a
 
      11-29-2003
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
http://www.velocityreviews.com/forums/(E-Mail 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[i]=temp[i];
delete [] temp;
}
 
Reply With Quote
 
 
 
 
David Rubin
Guest
Posts: n/a
 
      11-29-2003
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."

 
Reply With Quote
 
 
 
 
Evan
Guest
Posts: n/a
 
      11-29-2003
(E-Mail Removed) (Kevin King) wrote in message news:<(E-Mail Removed). 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
> (E-Mail 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[i]=temp[i];
> delete [] temp;
> }

 
Reply With Quote
 
Elie Nader
Guest
Posts: n/a
 
      11-29-2003

"Kevin King" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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
> (E-Mail 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[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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Merge Sort in C - array output is same as input after sort routine completes rkk C Programming 9 09-24-2006 08:30 PM
inputs for merge-sort vizziee@gmail.com VHDL 1 03-31-2005 12:35 PM
VHDL implementation of merge-sort vizziee@yahoo.com VHDL 2 01-04-2005 09:42 AM
Ado sort error-Ado Sort -Relate, Compute By, or Sort operations cannot be done on column(s) whose key length is unknown or exceeds 10 KB. Navin ASP General 1 09-09-2003 07:16 AM
Merge Sort question Seth G. Java 10 08-15-2003 12:02 AM



Advertisments