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?