Merge sort logic failure in allocating memory.

I am working on an implementation of merge-sort which will sort a list of songs by their length. I have written the following and have been unable to fins the flaw in my logic. Instead of returning a sorted list these functions return a list of one item from the middle of the original list.

vector<song> merge( vector<song> firstList, vector<song> secondList){
 vector<song> outPut;
 int i = 0; int n = 0;
 while( outPut.size() < (firstList.size() + secondList.size()-1 )){
    if( firstList[i].length < secondList[n].length){
        outPut.push_back( firstList[i]);
        i++;
    }else{
        outPut.push_back( secondList[n]);
        n++;
    }
 }
return outPut;
}
vector<song> mergeSortLength( vector<song> playlist){
 int scope = playlist.size()/2;
 vector<song> firstHalf( &playlist[0], &playlist[scope]);
 vector<song> secondHalf( &playlist[scope], &playlist[playlist.size()]);
 if ( firstHalf.size() != 1){
    firstHalf = mergeSortLength(firstHalf);
 }
 if ( secondHalf.size() != 1){
    secondHalf = mergeSortLength( secondHalf);
 }
 return merge( firstHalf, secondHalf);
}

If I change the while loop condition from

( outPut.size() < (firstList.size() + secondList.size() -1)){ 

to

( outPut.size() < (firstList.size() + secondList.size())){

it gets about halfway though the list sorting successfully until the compiler spits out:

playList(27898,0x7fff78b7b000) malloc: * mach_vm_map(size=7526769998340063232) failed (error code=3) * error: can't allocate region *** set a breakpoint in malloc_error_break to debug libc++abi.dylib: terminating with uncaught exception of type std::bad_alloc: std::bad_alloc Abort trap: 6

I really appreciate anyones help. My eyes are going fuzzy from staring at this.

---

In merge(), the code doesn't check to see if the end of a vector has been reached, specifically, if i >= firstList.size() or n >= secondList.size(), in which case the remainder of the other vector would be copied. The while statement should not have the -1 near the end.

VS complains about the temp vector creation using &playlist[playlist.size()], since the subscript is out of range. An optional way to do this is to use begin() + index, which is an iterator:

    vector<song> firstHalf( playlist.begin()+0, playlist.begin()+scope);
    vector<song> secondHalf( playlist.begin()+scope, 
                 playlist.begin()+playlist.size());

It's been over a day, so posting a fixed version in case anyone is interested. All that vector creation and push backs add a lot of overhead, it would have been better to do a one time allocation, and then just use iterators or indices to deal with the sub-vectors.

vector<song> merge( vector<song> firstList, vector<song> secondList){
    vector<song> outPut;
    size_t i = 0; size_t n = 0;
    while( outPut.size() < (firstList.size() + secondList.size()) ){
        if( firstList[i].length < secondList[n].length){
            outPut.push_back( firstList[i]);
            if(++i >= firstList.size()){
                do
                    outPut.push_back( secondList[n]);
                while(++n < secondList.size());
                break;
            }
        }else{
            outPut.push_back( secondList[n]);
            if(++n >= secondList.size()){
                do
                    outPut.push_back( firstList[i]);
                while(++i < firstList.size());
                break;
            }
        }
    }
    return outPut;
}

vector<song> mergeSortLength( vector<song> playlist){
    size_t scope = playlist.size()/2;
    vector<song> firstHalf( playlist.begin()+0, playlist.begin()+scope);
    vector<song> secondHalf( playlist.begin()+scope, playlist.begin()+playlist.size());
    if ( firstHalf.size() != 1){
        firstHalf = mergeSortLength(firstHalf);
    }
    if ( secondHalf.size() != 1){
        secondHalf = mergeSortLength( secondHalf);
    }
    return merge( firstHalf, secondHalf);
}

---

I didn't see with a lot of attention, but maybe you want

vector<song> secondHalf( &playlist[scope+1], &playlist[playlist.size()-1]);

the &playlist[playlist.size()] without -1 I think is the source of your problem, but I have not tried.

链接地址: http://www.djcxy.com/p/53492.html

上一篇: 合并排序函数的递归很混乱

下一篇: 分配内存时合并排序逻辑失败。