Thread: 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.

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.

Originally Posted by tabstop

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?

Code:

i = n1-1;
j = n1-1;

Oops!

Originally Posted by tabstop

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.