So I've implemented merge sort which, for all intends and purposes, could also be a custom sort function and I've started turning it into a template function.
Where I've run into a problem is when I wanted to add to possibility of passing a custom compare function in order to sort in different ways. (eg. std::greater and std::less or any custom one).
I've verified that the sorting algorithm works when I'd replace the ints by T. How would I add the custom compare function from here in order to also sort custom objects etc?
template < typename T,
class Compare>
void merge( vector<T> &arr, int start, int mid, int end, Compare comp )
{
int lptr = start;
int rptr = mid+1;
int tempptr = 0;
vector<T> temp( end - start + 1 );
for ( int i = 0; i<temp.size(); i++)
{
if ( lptr > mid ) //done with left-section, just move the right elements
{
temp[tempptr] = arr[rptr];
rptr++;
} else if ( rptr > end ) //done with right-section, just move the left elements
{
temp[tempptr] = arr[lptr];
lptr++;
} else if ( comp( arr[rptr], arr[lptr] )) // right item < left item, move right item
{
temp[tempptr] = arr[rptr];
rptr++;
} else //otherwise left item < right item, move left item
{
temp[tempptr] = arr[lptr];
lptr++;
}
tempptr++;
}
for ( int i = 0; i<temp.size(); i++)
{
arr[start + i] = temp[i];
}
}
template < typename T,
class Compare>
void mergeSort( vector<T> &arr, int start, int end, Compare comp)
{
//if we're down to single elements, do nothing
if ( start < end ){
//call to right and left 'child'
int mid = (start + end) / 2;
mergeSort( arr, start, mid );
mergeSort( arr, mid + 1, end );
//call to merge
merge( arr, start, mid, end );
}
}
int main()
{
vector<float> arr = {7,8, 2, 6.6, 1, 4.1, 5, 3, 8, 9};
cout << "before sorting:" << endl;
for ( auto n : arr )
cout << n << ", ";
cout << endl;
mergeSort( arr, 0, arr.size() - 1);
cout << "after sorting:" << endl;
for ( auto n : arr )
cout << n << ", ";
cout << endl;
return 0;
};
Thanks in advance.
Aucun commentaire:
Enregistrer un commentaire