Merge-sort issue!

This is a discussion on Merge-sort issue! within the C Programming forums, part of the General Programming Boards category; yo yo sup? so I get this Merge-Sort to be implemented in c,look: **Please notes this:1-The arrays are not sorted ...

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    17

    Merge-sort issue!

    yo yo sup?
    so I get this Merge-Sort to be implemented in c,look:

    **Please notes this:1-The arrays are not sorted and still I got to merge them.

    2-Running time must be of order O(n*log(n))
    3-The following code works but I get Runtime Error,so mainly I need your help to find out where the Runtime Error occurs!
    4-the two arrays of the same size


    Code:
    int merge_sort(int arr1[], int n)
    {
    int len;
    int*temp_array,*base;temp_array=(int*)malloc(sizeof(int)*n);
    if(temp_array==NULL){
        printf("Dynamic Allocation Error in merge_sort");
        return FAILURE;
        }
        for(len=1;len<n;len*=2){
            for(base=arr1;base<arr1+n;base+=2*len){
                  merge(base,len,base+len,len,temp_array);
                  memcpy(base,temp_array,1*len*sizeof(int));
                }
            }
        free(temp_array);
        return SUCCESS;
    }
    void merge(int a[],int na,int b[],int nb,int c[])
    {
     int ia,ib,ic;
     for(ia=ib=ic=0;(ia<na) && (ib<nb);ic++){
        if(a[ia]<b[ib]){
            c[ic]=a[ia];
            ia++;
            }
            else{
                c[ic]=b[ib];
                ib++;
                }
        }
        for(;ia<na;ia++,ic++)c[ic]=a[ia];
        for(;ib<nb;ib++,ic++)c[ic]=b[ib];
    }

    as u see i implemented merge too,

    My problem is that this code works for arrays of length of power to 2,I need it to work for any length of an array,(in the first 'for' loop)


    what u think?


    Thanks!
    Last edited by Kadmany; 05-28-2011 at 11:45 AM.

  2. #2
    Registered User
    Join Date
    Mar 2011
    Posts
    17
    man I am trying my best but still unable to to make this work for any length of an array,plz help !

  3. #3
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    975
    I suggest rereading a description of merge sort. Make sure you understand how it works before you try implementing it.

    The entire point of merge sort is that it's a divide and conquer algorithm--it's recursive. That means that merge_sort() should be calling itself.

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Kadmany View Post
    man I am trying my best but still unable to to make this work for any length of an array,plz help !
    In addition to the advice from Cas --whom I agree with-- you probably should turn off the computer and work the problem with pencil and paper until you understand it. As others here correctly advise: if you can't verbalize the solution, you don't actually understand the problem.

    Once you reach that point, tapping out the code should be rather easy.

    Try this on for size... (No need to post it here, this is for yourself)...
    In words --not code-- write a step by step description of what your merge sort has to do.

  5. #5
    Registered User
    Join Date
    Mar 2011
    Posts
    17
    Quote Originally Posted by CommonTater View Post
    In addition to the advice from Cas --whom I agree with-- you probably should turn off the computer and work the problem with pencil and paper until you understand it. As others here correctly advise: if you can't verbalize the solution, you don't actually understand the problem.

    Once you reach that point, tapping out the code should be rather easy.

    Try this on for size... (No need to post it here, this is for yourself)...
    In words --not code-- write a step by step description of what your merge sort has to do.
    Hey everyone,thanks for help,but I must mentiona few things,this code was taken from a lecture,it was designed for array which their length is of the power 2,it should work fine the only thing is must be modified if the loop for and small thing,If you know a better solution to find two common numbers of the two array of time O(n*log(n)) then I will be happy to know that!

  6. #6
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    975
    You probably should have explained the requirements in your first post; it only said that the problem is that this works for powers of 2 (which I hardly see as a problem, if that's the goal of the sort...)

    Anyway, I see now how this approach is supposed to work, knowing that it's for power-of-two sized arrays only. It's a rather interesting way of converting a recursive algorithm to an iterative one. Yet the only substantive issue you've raised, that I can see, is that you get a runtime error. In such cases, your first stop should be a debugger. I recommend Valgrind if it's available for your platform; otherwise, use whatever native debugger you have (gdb, xdb, etc).

    However, I still recommend learning how merge sort works. Once you understand merge sort, you should be able to see how it can be optimized for a power-of-two sized array. Then you'll understand what this algorithm is supposed to be doing.

  7. #7
    Registered User
    Join Date
    Mar 2011
    Posts
    17
    Quote Originally Posted by cas View Post
    You probably should have explained the requirements in your first post; it only said that the problem is that this works for powers of 2 (which I hardly see as a problem, if that's the goal of the sort...)

    Anyway, I see now how this approach is supposed to work, knowing that it's for power-of-two sized arrays only. It's a rather interesting way of converting a recursive algorithm to an iterative one. Yet the only substantive issue you've raised, that I can see, is that you get a runtime error. In such cases, your first stop should be a debugger. I recommend Valgrind if it's available for your platform; otherwise, use whatever native debugger you have (gdb, xdb, etc).

    However, I still recommend learning how merge sort works. Once you understand merge sort, you should be able to see how it can be optimized for a power-of-two sized array. Then you'll understand what this algorithm is supposed to be doing.
    Hey man,I think I better fix my english :P,No,I ment that the algorithm is designed for power-of-two arrays only,I need that for any poer-of-number hehe

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by Kadmany View Post
    Hey everyone,thanks for help,but I must mentiona few things,this code was taken from a lecture,it was designed for array which their length is of the power 2,it should work fine the only thing is must be modified if the loop for and small thing,If you know a better solution to find two common numbers of the two array of time O(n*log(n)) then I will be happy to know that!
    It is indeed not particularly hard to make that breadth-first merge sort code work for non-powers of two. It's simply a matter of passing the right arguments into merge to not overflow the array bounds. Right now you're passing in "len" and "len" as the lengths of the subarrays, Instead of pasing "len" for the length of the second subarray to merge, you pay attention to when "base+len (where the second half starts) + len" would exceed n, and pass in a different value for the second array length that does not exceed n.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Mar 2011
    Posts
    17
    Quote Originally Posted by iMalc View Post
    It is indeed not particularly hard to make that breadth-first merge sort code work for non-powers of two. It's simply a matter of passing the right arguments into merge to not overflow the array bounds. Right now you're passing in "len" and "len" as the lengths of the subarrays, Instead of pasing "len" for the length of the second subarray to merge, you pay attention to when "base+len (where the second half starts) + len" would exceed n, and pass in a different value for the second array length that does not exceed n.
    Hey IMalc,I think I understand what you sayin,the only thing is what should I change the base + len to? Could you please write me the same two for loops with the right argument passing?

    Thank you very much ahead!

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    I don't think you actually need to change base+len. If base+len is not less than n then don't call merge at all. If only the first of the two subarray's fits below n, then there is nothing to merge it with.

    Looking at my own implementation of this that I wrote ages ago, there is only two if-statements added, at least in terms of the difference to cyclomatic complexity. One is what I mentioned in my other post and one is what I mentioned in this post.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Mar 2011
    Posts
    17
    Quote Originally Posted by iMalc View Post
    I don't think you actually need to change base+len. If base+len is not less than n then don't call merge at all. If only the first of the two subarray's fits below n, then there is nothing to merge it with.

    Looking at my own implementation of this that I wrote ages ago, there is only two if-statements added, at least in terms of the difference to cyclomatic complexity. One is what I mentioned in my other post and one is what I mentioned in this post.
    Hey man thanks again,I gotta say,i have already mentioned that I know there is an error in for loop plus I gotta improve it,I am just unable to geuss whaat these conditions!!
    Couldnt you please just post them or send me a link to your written code? I am very tight in time And I WOULD REALLY APPRECIATE IT IF YOU HELP.

  12. #12
    Registered User
    Join Date
    Mar 2011
    Posts
    17

    Guys no one wants to helppppppp?????? :((((

    Guys plz whats the modifications must be done?

  13. #13
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    975
    I am just unable to geuss whaat these conditions!!
    There's the crux of your issue. You're unwilling to learn how merge sort works, instead trying to guess, and when that fails, get others to do your work for you.

    Go read about merge sort. Take a pencil and paper and do a merge sort, by hand, of a small list. Start with a power of 2 (try 8 elements) and figure out how your original code works (or is supposed to work). Once you understand that, it'll be easier to figure out how to sort any sized list with an iterative approach.

    You're probably not going to get somebody to do your homework for you, so I'd recommend not begging for it.

  14. #14
    Registered User
    Join Date
    Mar 2011
    Posts
    17
    Quote Originally Posted by cas View Post
    There's the crux of your issue. You're unwilling to learn how merge sort works, instead trying to guess, and when that fails, get others to do your work for you.

    Go read about merge sort. Take a pencil and paper and do a merge sort, by hand, of a small list. Start with a power of 2 (try 8 elements) and figure out how your original code works (or is supposed to work). Once you understand that, it'll be easier to figure out how to sort any sized list with an iterative approach.

    You're probably not going to get somebody to do your homework for you, so I'd recommend not begging for it.
    Its not to do my homework,here is what I know about merge-sort:
    You get an array with random values in cells,You divide the array into two,then each part divided you divide again into two you keep doin that tell you get single elements,then you merge those with the other element which both of them splitted,you do that again with the other part from where these two part splitted you keep doing that tell you get the array sorted,

    I am just unable to figure out a way to modify the code even though I understand that basically if the length of the array isnt of power two is to to try to split it into two parts where on of them is of power two,,,,

    In addition,DUE to your kindness and very very supportive approach I have been trying to expand the array in case its length is not of power two:

    Code:
      int i,closest_length_of_power_two,max;
      int *temp_array;
    
     if(!is_power_of_two(n)){
           closest_length_of_power_two=get_closest_length_of_power_two(n);
           max=find_max_in_array(arr2,n);
           temp_array=creat_new_array(closest_length_of_power_two);
           if(temp_array==NULL){
               printf("Dynamic Allocation Error in creat_new_array");
               return -1;
             }
           for(i=0;i<closest_length_of_power_two;i++){
                 if(i<n){
                    *(temp_array+i)=arr2[i];
                   }
                 if(i>=n){
                    *(temp_array+i)=max+1;
                   }
                }
            if(merge_sort(temp_array,closest_length_of_power_two)==1){
                 for(i=0;i<closest_length_of_power_two;i++){
                      if(binary_search(temp_array,n,arr1[i])==1){
                          free(temp_array);
                          return 1;
                        }
                     }
               }
           }
    and:

    Code:
    int* creat_new_array(int closest_length_of_power_two)
    {
       int *temp_array;
       temp_array=(int*)malloc(sizeof(int)*(closest_length_of_power_two));
    
       return temp_array;
    }
    Notes:fucntion get_closest_length_of_power_two gets the smallest biggest power of two to the given array size,

    Now I am still getting Runtime Error! why's that?
    Last edited by Kadmany; 05-30-2011 at 04:15 PM.

  15. #15
    Registered User
    Join Date
    Mar 2011
    Posts
    17
    Guys,no any ideas?

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge sort fails to sort
    By Cresh07 in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2009, 11:17 AM
  2. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 05:48 PM
  3. Merge Sort Help
    By blindman858 in forum C++ Programming
    Replies: 5
    Last Post: 05-14-2005, 09:47 PM
  4. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  5. merge sort and selection sort and time spent on both
    By misswaleleia in forum C Programming
    Replies: 3
    Last Post: 06-04-2003, 02:24 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21