mercredi 28 mars 2018

How to add a comparator to a custom sort function

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