问题描述:

I have implemented merge sort using recursion. The code for the two functions involved is below:

void merge(int la[50],int ra[50],int lsize,int rsize)

{

cout<<"\nLEFT Array\n";

for(int i=0;i<lsize;i++)

{

cout<<la[i]<<" ";

}

cout<<"\nRIGHT Array\n";

for(int i=0;i<rsize;i++)

{

cout<<ra[i]<<" ";

}

int a[100],i,j,k;

i=0;

j=0;

k=0;

while((i<lsize)&&(j<rsize))

{

if(la[i]<ra[j])

{

a[k]=la[i];

k++;

i++;

}

else

{

a[k]=ra[j];

k++;

j++;

}

}

while(i < lsize)

{

a[k]=la[i];

k++;

i++;

}

while(j < rsize)

{

a[k]=ra[j];

k++;

j++;

}

cout<<"\nMERGED\n";

for(int i=0;i<k;i++)

{

cout<<a[i]<<" ";

}

}

void mergesort(int a[100],int n)

{

if(n == 1)

{

return;

}

else

{

int ra[50],la[50],lsize,rsize;

lsize = n/2;

rsize = n-lsize;

cout<<"\nLA\n";

for(int i=0;i<lsize;i++)

{

la[i]=a[i];

cout<<la[i]<<" ";

}

cout<<"\nRA\n";

for(int i=0;i<rsize;i++)

{

ra[i]=a[lsize+i];

cout<<ra[i]<<" ";

}

mergesort(la,lsize);

mergesort(ra,rsize);

merge(la,ra,lsize,rsize);

}

}

However, during the recursion process, if the merged sub-array is for example 1,2,5, then the next time it is used in the merged function, the array gets used as 2,1,5 or something else randomly. Hence, I do not get the correct output for the sort. For instance, I entered the unsorted array as 3,5,1,4,2.

Here what happens is that the merge sort proceeds correctly till the stage where one of my merged array 2,4 that is formed during the merge function, becomes 4,2 when it used to calculate the bigger sub-array. Hence the merge sort goes wrong. Please help me out on where I am going wrong.

网友答案:

There are numerous things wrong, starting with there is no actual merging being done. You "merge" into a local array a[100] in your merge() function, the proceed to do absolutely nothing with that hard-earned effort whatsoever. The caller-side remains unchanged, and that, as they say, is that.

Second, the fixed sizes in this should NOT be present. the algorithm is, by its definition, designed to handle arbitrary lengths, and should be implemented as such.

Several things about the mergesort algorithm are fundamental. Unless you are armed with a particularly impressive in-place merge algorithm (they do exist, but they are not trivial), you will be doing one of two operations for splitting or merging your data:

  • Split the current list into two sublists, copying each to temp storage, then recursing, then merging those two temp segments back to the original list as the recursing unrolls.
  • Split the current list by marker only, passing each list+length through the recursion, and merge into temp storage, then copy into your original container.

In short, you can either (a) split to temp storage, recurse, merge to original, or (b) index-only-split, recurse, merge to temp, copy to original. The choice is yours. Below is an algorithm that does the later, and if you're not surprised at the simplicity, you should be (but there is an even better way which I will show last):

#include <algorithm>
#include <vector>

void mergesort(int arr[], size_t N)
{
    if (N <= 1)
        return;

    size_t mid = N/2;
    mergesort(arr, mid);
    mergesort(arr+mid, N-mid);

    std::vector<int> temp(N);
    std::merge(arr, arr+mid, arr+mid, arr+N, temp.begin());
    std::copy(temp.begin(), temp.end(), arr);
}

A sample program that uses the above algorithm follows:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <random>

void mergesort(int arr[], size_t N)
{
    if (N <= 1)
        return;

    size_t mid = N/2;
    mergesort(arr, mid);
    mergesort(arr+mid, N-mid);

    std::vector<int> temp(N);
    std::merge(arr, arr+mid, arr+mid, arr+N, temp.begin());
    std::copy(temp.begin(), temp.end(), arr);
}

int main()
{
    std::random_device rd;
    std::default_random_engine rng(rd());
    std::uniform_int_distribution<int> dist(1,100);

    int arr[25];
    std::generate_n(arr, 25, [&](){ return dist(rng); });

    // copy to stdout
    std::copy(std::begin(arr), std::end(arr),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    // mergesort
    mergesort(arr, 25);

    // copy to stdout
    std::copy(std::begin(arr), std::end(arr),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    return 0;
}

Output (yours will obviously vary)

98 91 87 25 60 41 16 18 10 72 68 35 16 80 46 17 56 44 78 92 57 63 66 82 63 
10 16 16 17 18 25 35 41 44 46 56 57 60 63 63 66 68 72 78 80 82 87 91 92 98 

The C++ Approach with In-Place Merging

Remember that comment about how particularly nice it would be to have an in-place merge algorithm? Well guess what? The C++ standard library provides one: std::inplace_merge. This makes our mergesort algorithm rival insertion-sort in its triviality:

void mergesort(int arr[], size_t N)
{
    if (N <= 1)
        return;

    size_t mid = N/2;
    mergesort(arr, mid);
    mergesort(arr+mid, N-mid);
    std::inplace_merge(arr, arr+mid, arr+N);
}
相关阅读:
Top