Divide and Conquer Merge_sort

This is a discussion on Divide and Conquer Merge_sort within the C++ Programming forums, part of the General Programming Boards category; This code is supposed to sort an array using the divide-and-conquer method. But I think I mixed up the index. ...

  1. #1
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    455

    Divide and Conquer Merge_sort

    This code is supposed to sort an array using the divide-and-conquer method. But I think I mixed up the index.
    Code:
    #include <iostream>
    
    using namespace std; 
    
    void Merge(float *A , int p , int q , int r)
    {
      int n1 = q - p + 1;
      int n2 = r - q;
      float *L = new float [n1];
      float *R = new float [n2];
      int i , j;
      for ( i = 0 ; i < n1 ; i++)
        L[i] = A[p + i -1];
       
      for ( j = 0 ; j < n2 ; j++)
        R[j] = A[q + j];
        
    
      i = 1;
      j = 1;
    
      for ( int k = p; k <= r ; k++)
        {
          if ( L[i] <= R[j])
    	{
    	  A[k] = L[i];
    	  ++i;
    	}
          else if (A[k] == R[j])
    	{
    	  ++j;
    	}
        }
     
      delete [] L;
      delete [] R;
    }
    
    void Merge_Sort(float *A, int p, int r)
    {
      if ( p < r )
        {
          int q = (p+r)/2;
          Merge_Sort(A,p,q);
          Merge_Sort(A,q+1,r);
          Merge(A,p,q,r);
        }
    }
    
        
    
    int main()
    {
      int n = 8;
      float A[] = {5,2,4,7,1,3,2,6};
      for ( int i = 0 ; i < 8 ; i++)
        std::cout << A[i] << std::endl;
      Merge_Sort(A,1,7);
      cout << endl;
      for ( int i = 0 ; i < 8 ; i++)
        std::cout << A[i] << std::endl; 
      return 0;
    }
    The array to be sorted is:
    Code:
    A={5,2,4,7,1,3,2,6}
    the sorted array should be:
    Code:
    1 2 2 3 4 5 6 7
    However, what i get is:
    Code:
    5 0 0 0 0 0 0 6
    This is just replacing the point in the middle of the original array A with 0. I don't understand why it's doing this. Any input is well appreciated.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    All your array indices appear to be one off, but not really in a consistent manner. You start things at 1 instead of 0, you split A[q] with the first group, but your merge uses A[q] as the first element in the second group. And so on.

  3. #3
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    455
    Quote Originally Posted by tabstop View Post
    All your array indices appear to be one off, but not really in a consistent manner. You start things at 1 instead of 0, you split A[q] with the first group, but your merge uses A[q] as the first element in the second group. And so on.
    I've been working on this to fix the indexing.
    Code:
    #include <iostream>
    
    using namespace std; 
    
    void Merge(float *A , int p , int q , int r)
    {
      int n1 = q - p + 1;
      int n2 = r - q;
      float *L = new float [n1];
      float *R = new float [n2];
      int i , j;
      for ( i = 0 ; i < n1 ; i++)
        {
          L[i] = A[p + i];
        }
    
      
      for ( j = 0 ; j < n2 ; j++)
        {
          R[j] = A[q+1+j];
        }
      
      i = n1-1;
      j = n1-1;
     
      for ( int k = r; k >= p ; k--)
        {
          if ( L[i] >= R[j] )
    	{
    	  A[k] = L[i];
    	  L[i] = 0;
    	 
    	  if( (i-1) >= 0)--i;
    	}
          else
    	{
    	  A[k] = R[j];
    	  R[j] = 0;
    	  if( (j-1) >= 0) --j;
    	}
        }
      delete [] L;
      delete [] R;
      
    }
    
    
    void Merge_Sort(float *A, int p, int r)
    {
      if ( p < r )
        {
          int q = (p+r)/2;
          //cout << "p=" << p << " q=" << q <<  " r=" << r << endl;
          Merge_Sort(A,p,q);
          Merge_Sort(A,q+1,r);
          Merge(A,p,q,r);
        }
    }
    
        
    
    int main()
    {
     
      float A[] = {30,20,25,52,32,26,78,79,2,3};
      // int n = sizeof(A)/sizeof(float);
      int n=10;
      cout << n << endl;
      
      for ( int i = 0 ; i < n ; i++)
        std::cout << A[i] << "   ";
      cout << endl;
      
      Merge_Sort(A,0,7);
    
      cout << endl;
    
      for ( int i = 0 ; i < n ; i++)
        std::cout << A[i] << " ";
      cout << endl; 
      return 0;
    }
    The strange thing is, this will only works if I sort 8 elements in the array. If I choose to sort more element, it won't work and some value of A is changed to 0.
    What's wrong with this?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Code:
    i = n1-1;
    j = n1-1;
    Oops!

  5. #5
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    455
    Quote Originally Posted by tabstop View Post
    Code:
    i = n1-1;
    j = n1-1;
    Oops!
    Thank you. That was such a stupid mistake. I thought of using n2,, but still put down n1.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Divide and Conquer: array in the reverse order
    By Steamer in forum C Programming
    Replies: 11
    Last Post: 03-08-2004, 06:31 PM
  2. divide and conquer
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 06-13-2002, 09:52 AM

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