I have implemented the following mergeSort function in C++. For some reason, it
ID: 3887710 • Letter: I
Question
I have implemented the following mergeSort function in C++. For some reason, it sorts both sides of the array but does not merge the two back properly. Any help is appreciated
int mergeSort(empType A[], int first, int last)
{
int mid = (first + last + 1) / 2; // get midpoint
int comp = 0; // holds # of comparisons
empType tempArray;
// Loop to middle, start at first + 1
for (int i = first + 1; i < mid; i++)
{
// if given score < previous
if (A[i].Score < A[i - 1].Score)
{
// set j = what i is at in original for loop
// loop to first + 1 and decrement
for (int j = i; j > first + 1; j--)
{
// if element's score < previous
if (A[j].Score < A[j - 1].Score)
{
tempArray.ID = A[j].ID; // Put ID into tempArray
tempArray.Score = A[j].Score; // Put Score into tempArray
A[j].ID = A[j - 1].ID; // Move on to next ID element
A[j].Score = A[j - 1].Score; // Move on to next Score element
A[j - 1].ID = tempArray.ID; // Put next ID into tempArray
A[j - 1].Score = tempArray.Score; // Put next Score into tempArray
comp++; // Increase computations
}
}
}
}
// loop from middle to last elements
for (int i = mid; i < last; i++)
{
// if current score < previous
if (A[i].Score < A[i - 1].Score)
{
for (int j = i; j > mid + 1; j--)
{
if (A[j].Score < A[j - 1].Score)
{
tempArray.ID = A[j].ID;
tempArray.Score = A[j].Score;
A[j].ID = A[j - 1].ID;
A[j].Score = A[j - 1].Score;
A[j - 1].ID = tempArray.ID;
A[j - 1].Score = tempArray.Score;
comp++;
}
}
}
}
return comp; // return the number of comparisons
}
Explanation / Answer
There are 2 parts to the code: 1 which tries to sort the first part of the array and second which sorts the second half of the array.
There needs to be a third part ( just before retun comp;) which merges the 2 halves of array A intoo a single sorted array.Essentially it would involve:
1) 2 pointers at the start of each half of the array-ptr1,ptr2
2) Create a temp array callled tA.
3) Compare the elements corresponding to A[ptr1],A[ptr2].Insert the smaller of the 2 elements into tA and increment the corresponding pointer.
4) Repeat 3 till all elements of both halves are covered.
5)Copy tA to A and remove tA.
6) A now contains sorted array.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.