magicleon magicleon - 1 year ago 62
C++ Question

c++ merge sort not working and crashing

I was trying to implement merge sort in c++ in the following way:

#include <iostream>
using std::cout;
using std::endl;
using std::string;
using std::memcpy;

void mergeSort(int *array, int *temp, int leftStart, int rightEnd);
void mergeHalves(int *array, int *temp, int leftStart, int rightEnd);

void printArray(int* array, int size,string message){
cout<<message<<endl;
for (int i = 0; i < size; i++)
cout << *(array+i) << "\t";
cout << endl;
}
int main(){
const int size = 10;
int myInts[size] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
int temp[size] = {0};
printArray(myInts,size,"Input");
mergeSort(myInts, temp, 0, size-1);
printArray(myInts, size, "Output:");

return 0;
}

void mergeSort(int *array, int *temp, int leftStart, int rightEnd){
if (leftStart >= rightEnd)
return;

int middle = (leftStart + rightEnd) / 2;

mergeSort(array, temp, leftStart, middle);
mergeSort(array, temp, middle + 1, rightEnd);
mergeHalves(array,temp,leftStart,rightEnd);
return;
}

void mergeHalves(int *array, int *temp, int leftStart, int rightEnd){
int leftEnd = (rightEnd + leftStart) / 2;
int rightStart = leftEnd + 1;
int size = rightEnd - leftStart + 1;

int left = leftStart;
int right = rightStart;
int index = leftStart;

while (left <= leftEnd && right <= rightEnd){
if (*(array+left) <= *(array+right)){
*(temp+index) = *(array+left);
left++;
}else{
*(temp+index) = *(array+right);
right++;
}
index++;
}

memcpy(temp + index, array + left, (leftEnd - left + 1) * sizeof(int));
memcpy(temp + index, array + right, (rightEnd - right + 1) * sizeof(int));
memcpy(array, temp, size * sizeof(int));
}


I have checked the code more and more times and I cannot manage to understand what I am missing.

The algorithm was not working properly with an initial value of

myInts[size] = {3, 6, 4, 2, 7, 8, 9, 1, 0, 5}


as it sorted only the first half of the array.

Then I tried to change the input with the one shown in the code, and I got the following output:

Input
9 8 7 6 5 4 3 2 1 0
Output:
3 2 1 0 -161742639 6 5 4 7 8
Abort trap: 6


After a while I recompiled and ran THE SAME CODE and got this output instead:

Input
9 8 7 6 5 4 3 2 1 0
Output:
3 2 1 0 6 5 4 7 8 9


It seems to me that some assignment operation or copy operation went wrong and at random too, but everything seems right to me..


I've tried with step by step debugging and the flow of the program seems ok.


I'm running on MacOS X Sierra 10.12.6, I'm compiling with g++.


What am I missing? I'm getting crazy.. Thanks in advance!


EDIT: I seem to have solved the
Abort Trap
problem, I edited the code passing
size-1
instead of
size
in the
main
function. Still ordering does not work though

Answer Source

After a LOT of debugging for you, I've found your issue. You have named multiple variables the same thing through your different functions. Some of these variables mean exactly the same thing (leftStart, rightEnd), while others, like size mean two completely different things.

At the end of mergHalves, you do memcpy(array, temp, size * sizeof(int)); probably because you were thinking size is the size of the whole array so you're copying everything back over. However, it's not.

That line should be memcpy(array+leftStart, temp+leftStart, size * sizeof(int)); since in this function you've declared size to be int size = rightEnd - leftStart + 1;. This is a good example of why making your variable names a little longer and more descriptive can save you a few hours of debugging (and having to post on StackOverflow).

See the fix in action on ideone.

Lastly, as an aside, I understand that you want to try doing this "the hard way," without vectors, but please please please don't ever do something like *(temp+index). The subscript operator was made for that exact purpose and means the exact same thing, just a lot more readable. (ie, do temp[index] instead).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download