Algorithm: Can you Help me with my MergeSort implementation?

This is a discussion on Algorithm: Can you Help me with my MergeSort implementation? within the C++ Programming forums, part of the General Programming Boards category; Hello there! Glad to be a new member here! I'm new to c++ coding, and I'm taking an algorithms course, ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    3

    Algorithm: Can you Help me with my MergeSort implementation?

    Hello there!

    Glad to be a new member here!

    I'm new to c++ coding, and I'm taking an algorithms course, and I've been having the hardest time implementing one of the basic Algorithms Merge-Sort, For those who recall how it works; My Merge-Step works fine

    Code:
    void merge(vector<int> array, int p, int q, int r) {
      int n1 = q - p + 1;
      int n2 = r - q;
    
    
      vector<int> left, right;
      vector<int>::iterator a_it = array.begin();
    
    
      for(int i = 0; i != n1; ++i)
        left.push_back(*(a_it + p + i -1));
      left.push_back(1000000); //sentinel
    
    
      for(int j = 0; j != n2; ++j)
        right.push_back(*(a_it + q + j));
      right.push_back(1000000); //sentinel
    
      array.clear();
    
      vector<int>::iterator i = left.begin(), j = right.begin();
      
      for(int k = 0; k < r; ++k) {    
        if(*i <= *j) {
          array.push_back(*i);
          ++i;
        } else {
          array.push_back(*j);
          ++j;
        }
      }
      
    }
    However my MergeSort recursive implementation does not work

    Code:
    void mergesort(vector<int> array, int p, int r) {
     if(p < r) {
        int q = floor((p + r) / 2);
        mergesort(array, p, q);
        mergesort(array, q + 1, r);
         merge(array, p, q, r - 1);
      }
    }
    The above code is based on the CLRS text book, So.. If I print the Array from within mergesort, it doesn't output the sorted array

    Can you help me? Can you possibly spot where are the errors? I'm truly clueless..

    Thanks in advance,

    Best Regards,

    J

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    The problem that immediately jumps out at me is that you are passing your vectors by value. This actually copies the whole vector and all of the items within it!
    You will need to pass the vector by reference.

    I haven't looked any further than that, because that completely and utterly prevents it from working in any way at all. Upon fixing that you will probably manage to make some progress on your own. Well see how it goes anyway.
    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"

  3. #3
    Registered User
    Join Date
    Feb 2013
    Posts
    3
    Hi, thanks for the reply,

    Actually, I had wondered if that was the problem myself. The only reason why I haven't made that change was because none of the similar examples I've seen in the web have reference params; However, I agree with you.. That has to be one of the main causes, If not the main cause for this malfunction. So, for argument's sake, where do you think I should pass a reference? in merge() or in mergesort();

    Thank you for your reply once more very kind of you.

  4. #4
    Registered User
    Join Date
    Oct 2006
    Posts
    2,539
    Quote Originally Posted by jlstr View Post
    where do you think I should pass a reference? in merge() or in mergesort();
    yes.

    also, p, q, and r are not very descriptive variable names, and it is impossible to determine what they do, without expending a significant amount of effort to understand your code.

  5. #5
    Registered User
    Join Date
    Feb 2013
    Posts
    3
    Code:
    void merge(vector<int> &array, int left, int middle, int right) { //zero based indexes
      int n1 = middle - left;
      int n2 = right - middle;
    
    
      vector<int> left_array, right_array; //two arrays are necessary; both are array/2
      vector<int>::iterator a_it = array.begin();
    
    
      for(int i = 0; i != n1; ++i)
        left_array.push_back(*(a_it + left + i));
      left_array.push_back(1000000); //sentinel
    
    
      for(int j = 0; j <= n2; ++j)
        right_array.push_back(*(a_it + right + j));
      right_array.push_back(1000000); //sentinel
    
    
      array.clear(); //NOT SURE IF I SHOULD DO THIS! But seems necessary or I'll just make a huge vector in each call
    
    
      vector<int>::iterator i = left_array.begin(), j = right_array.begin();
      
      for(int k = 0; k <= r; ++k) {    
        if(*i <= *j) {
          array.push_back(*i);
          ++i;
        } else {
          array.push_back(*j);
          ++j;
        }
      }
    
    
    }
    Code:
    void mergesort(vector<int> &array, int left, int right) { //left and right and indexes
    
    
     if(left < right) {
        int middle = floor((left + right) / 2);
        mergesort(array, left, middle);
        mergesort(array, middle + 1, r);
        merge(array, left, middle, right);
      }
    
    
    }
    Hi there! I have updated the code Sorry for the less than descriptive arguments, it was only because it's like that in most text-books.

    So, I asked this, but I think I mistyped.. Where should I use references? in merge()? OR in mergesort()? OR in both?

    Anyway, The merge() seems to be working well, it's the recursive mergesort() that seems to mess up the left and right args passed.

    Thanks again for the replies!

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Is there anywhere where you actually want the entire vector to be copied, such that anything done to the copy has no effect on the vector that was passed in?
    If not then there's nowhere where you want to pass it by value.

    Also, you should get rid of those "sentinels" - find another way. They are a flawed way to stop yourself running off the end of the vector.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 12-27-2012, 05:32 AM
  2. Replies: 8
    Last Post: 10-09-2011, 09:46 AM
  3. Implementation of path finder algorithm in C
    By user_name_void in forum C Programming
    Replies: 2
    Last Post: 11-23-2009, 12:31 AM
  4. Recuresive Mergesort Algorithm
    By Nawb in forum C++ Programming
    Replies: 3
    Last Post: 06-08-2003, 08:02 PM
  5. MergeSort implementation with linklist.
    By Kam in forum C Programming
    Replies: 3
    Last Post: 10-21-2002, 12:04 PM

Tags for this Thread


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