-1

I'm implementing the merge sort algorithm using C++. An exception(bad_alloc) is raised, while sorting larger arrays. Since i'm new to C++ i have no idea about how to get rid of this error. The answer i'm willing is not handling the exception, but the reason.

Here's my main method where i initially calls merge_sort function.

int *arr;

int main(){
        int limits[2]={10,10000000};            //numbers of elements that should be in an array at each iteration

        for(int l=0;l<sizeof(limits)/sizeof(*limits);l++){
                cout<<"\n"<<endl;
                arr=new int[limits[l]];
                for(int cnt=0;cnt<limits[l];cnt++){                             //creating the random array using random numbers
                        int temp=rand()%2147483647;
                        arr[cnt]=temp;
                }
                clock_t t;
                t=clock();
                cout<<"\nNumber of elements  :  "<<limits[l]<<endl;

                merge_sort(0,limits[l]-1);                              //calling the merge sort function
                cout<<endl;
                t=clock()-t;
                cout<<"The time taken :  "<<t<<endl;
                delete[] arr;
        }
        cin.get();
return 0;
}

Up to 1000000 elements this works fine. I'm having the trouble when sorting the array of size 10000000.

Here's the full code for test purposes.

#include<iostream>
#include<string.h>
#include<limits>
#include<time.h>
#include<stdlib.h>

using namespace std;
void merge_sort(int i,int j);
void merge(int i,int temp,int j);

int *arr;

//main method
int main(){
        int limits[2]={10,10000000};            //numbers of elements that should be in an array at each iteration
        for(int l=0;l<sizeof(limits)/sizeof(*limits);l++){
                cout<<"\n"<<endl;
                arr=new int[limits[l]];
                for(int cnt=0;cnt<limits[l];cnt++){                             //creating the random array using random numbers
                        int temp=rand()%2147483647;
                        arr[cnt]=temp;
                }
                clock_t t;
                t=clock();
                cout<<"\nNumber of elements  :  "<<limits[l]<<endl;

                merge_sort(0,limits[l]-1);                              //calling the merge sort function

                t=clock()-t;
                cout<<"The time taken :  "<<t<<endl;
                delete[] arr;
        }
        cin.get();
return 0;
}


//method implementing the merge sort algorithm
void merge_sort(int i,int j){
        if(i<j){
                int temp=(i+j)/2;
                merge_sort(i,temp);
                merge_sort(temp+1,j);
                merge(i,temp,j);
        }
        return;
}


//method implementing the merge algorithm
void merge(int i,int temp,int j){
        int n1=temp-i+2;                                    //calculating the sub array lengthes
        int n2=j-temp+1;
        int *L=NULL;
        int *R=NULL;
        L=new int[n1];                                      //dynamically initializing the sub left and right hand side arrays
        R=new int[n2];

        for(int x=0;x<n1-1;x++){
                L[x]=arr[i+x];
        }
        for(int y=0;y<n2-1;y++){
                R[y]=arr[temp+y+1];
        }
        L[n1-1]=numeric_limits<int>::max();                 //adding the largest possible integer to the end of each array
        R[n2-1]=numeric_limits<int>::max();
        int a=0;
        int b=0;
        for(int k=i;k<=j;k++){                              //merging the two sub arrays
                if(L[b]>R[a] ){
                        arr[k]=R[a];
                        a++;
                }
                else{
                        arr[k]=L[b];
                        b++;
                }
        }
}

It's better if someone can give me the reason behind this rather than a fix. Thanks!

4

1 回答 1

0

您的merge函数有内存泄漏，而且非常大：

L = new int[n1];    
R = new int[n2];

内存永远不会被释放。如果您来自 Java 或 C# 等语言，您会发现 C++ 的工作方式有所不同。没有自动垃圾收集，并且new[]在 C++ 中使用需要您delete[]在某些时候使用，否则会出现内存泄漏。

但更好的解决方案是将这些行替换为：

#include <vector>
//...
// Remove the int *L and int *R declarations.
//
std::vector<int> L(n1);
std::vector<int> R(n2);

您应该始终vector首先考虑使用new[]/delete[]以避免这些类型的内存错误。

进行这些更改后，程序将完成，但需要一段时间（至少在调试模式下使用 Visual Studio 2013 时是这样）。

在发布模式下，10000000 所用的时间是 3,300 毫秒。

编辑：对于一个实验，我使用以下代码来查看如果将向量移出函数并重新使用会发生什么：

std::vector<int> L;
std::vector<int> R;

void merge(int i, int temp, int j){
    int n1 = temp - i + 2;  
    int n2 = j - temp + 1;

    L.resize(n1);
    R.resize(n2);
//...
}

所以我将向量设为全局。它花费的时间接近 2,000 毫秒，因此快了大约 1,000 毫秒。优点是使用resize调整向量的大小，而不是重新声明它们，或者new[]/delete[]多次使用。

于 2014-11-29T02:48:00.367 回答