Верна ли моя реализация слияния с помощью компаратора? - PullRequest
Новая
       33

Верна ли моя реализация слияния с помощью компаратора?

0 голосов
/ 09 марта 2019

В настоящее время у меня есть функция bruteforce, функция слияния, к которой клиент / пользователь может получить доступ, другая функция слияния, к которой клиент / пользователь не имеет доступа, и функция слияния, которая вызывается в mergesort. Это все находится в моем файле sort.h 

template <typename Comparable, typename Comparator>
void mergeSort(vector<Comparable> & a,
    vector<Comparable> & tmpArray, int left, int right, Comparator cmp)
{
    if (cmp(left,right))
    {
        int center = (left + right) / 2;
        mergeSort(a, tmpArray, left, center, cmp);
        mergeSort(a, tmpArray, center + 1, right, cmp);
        merge(a, tmpArray, left, center + 1, right,cmp);
    }
}

template <typename Comparable, typename Comparator>

void mergeSort2(vector<Comparable> & a, Comparator cmp)

{
    vector<Comparable> tmpArray(a.size());
    mergeSort(a, tmpArray, 0, a.size() - 1, cmp);

}


template <typename Comparable, typename Comparator>
void merge(vector<Comparable> & a, vector<Comparable> & tmpArray,
    int leftPos, int rightPos, int rightEnd, Comparator cmp)
{
    int leftEnd = rightPos - 1;
    int tmpPos = leftPos;
    int numElements = rightEnd - leftPos + 1;

    // Main loop
    while ((cmp(leftPos, leftEnd)) && (cmp(rightPos, rightEnd)))

        if (cmp(a[leftPos], a[rightPos]))
            tmpArray[tmpPos++] = std::move(a[leftPos++]);
        else
            tmpArray[tmpPos++] = std::move(a[rightPos++]);


    while (cmp(leftPos,leftEnd))    // Copy rest of first half
        tmpArray[tmpPos++] = std::move(a[leftPos++]);

    while (cmp(rightPos,rightEnd))  // Copy rest of right half
        tmpArray[tmpPos++] = std::move(a[rightPos++]);

    // Copy tmpArray back
    for (int i = 0; i < numElements; ++i, --rightEnd)
        a[rightEnd] = std::move(tmpArray[rightEnd]);
}

Мои два компаратора: 

class CompareXCoordinate {
public:
    bool operator()(const Point & p1, const Point & p2) const
    {
        return (p1.getX() < p2.getX());
    }
};
class CompareYCoordinate {
public:
    bool operator()(const Point & p1, const Point & p2) const
    {
        return (p1.getY() < p2.getY());
    }
};

Вывод векторных точек перед mergeSort2: 

5.63585 0.0125126
8.08741 1.93304
4.79873 5.85009
8.95962 3.50291
7.46605 8.2284
8.58943 1.74108
5.13535 7.10501

Как только я вызываю mergeSort2 (points, Point :: CompareXCoordinate ()); Выход: 

0 0
0 0
0 0
0 0
0 0
0 0
0 0

Вместо сортировки по координатам X точек, это просто ноль? Это проблема с моей функцией слияния?

...