merge sort #of comparisons

Discussion in 'C++' started by Kevin King, Nov 29, 2003.

  1. Kevin King

    Kevin King Guest

    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



    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;
    }
     
    Kevin King, Nov 29, 2003
    #1
    1. Advertising

  2. Kevin King

    David Rubin Guest

    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."
     
    David Rubin, Nov 29, 2003
    #2
    1. Advertising

  3. Kevin King

    Evan Guest

    (Kevin King) wrote in message news:<>...
    > 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
    >


    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;
    > }
     
    Evan, Nov 29, 2003
    #3
  4. Kevin King

    Elie Nader Guest

    "Kevin King" <> wrote in message
    news:...
    > 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
    >
    >
    >
    > 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
     
    Elie Nader, Nov 29, 2003
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    4,539
  2. Replies:
    1
    Views:
    984
    Jonathan Bromley
    Mar 31, 2005
  3. Seth G.

    Merge Sort question

    Seth G., Aug 11, 2003, in forum: Java
    Replies:
    10
    Views:
    1,249
    Jordan Zimmerman
    Aug 15, 2003
  4. rkk
    Replies:
    9
    Views:
    827
    CBFalconer
    Sep 24, 2006
  5. Navin
    Replies:
    1
    Views:
    729
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page