0

Im trying to make this mergesort function to sort a vector or word nodes (contains word length, number of occurences, and the word itsself) It seems to enter the merge function once, then the program fails, any ideas?

bool Utility::mergeSort_occurences(vector<Word> &invector){
    if (invector.size() <= 1){
        return true;
    }
    vector<Word> left, right;
    int middle = (invector.size()/2);
    for(int i = 0 ; i < middle ; i++){
        left.push_back(invector[i]);
    }
    for(int i = middle ; i < invector.size() ; i++){
        right.push_back(invector[i]);
    }
    mergeSort_occurences(left);
    mergeSort_occurences(right);
    invector = mergeOccurences(left, right);
    return true;
}

vector<Word> Utility::mergeOccurences(vector<Word> &left, vector<Word> &right){
    vector<Word> mergelist;
    while(left.size() > 0 || right.size() > 0){
        if(left.size() > 0 && right.size() > 0){
            if(left[0].getOccurences() <= right[0].getOccurences()){
                mergelist.push_back(left[0]);
                left.erase(left.begin());
            }else{
                mergelist.push_back(right[0]);
                right.erase(right.erase(right.begin()));
            }
        }
        else if(left.size() > 0){
           mergelist.push_back(left[0]);
           left.erase(left.begin()); 
        }
        else if(right.size() > 0){
           mergelist.push_back(right[0]);
           right.erase(right.erase(right.begin()));            
        }
    }
    return mergelist;
}
1
  • 1
    Yes - you could debug it. Run through the code with your debugger using a trivially small dataset in your vector. Four values, say. It should then be reasonably easy to find out where the problem lies, much easier than, say, trying to spot the problem by staring at a pageful of complex vector/array handling code written by someone else. Commented Apr 10, 2012 at 1:18

1 Answer 1

1

Your right.erase(right.erase(right.begin())); code looks dodgy. The erase function returns an iterator to the successor of the element which was deleted, which is the end() if you deleted the last element.

You're guarding this code with right.size() > 0 which only guarantees there is one item. You have two erase operations.

Have you looked into the consequences of doing erase on right.end()?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.