Реализующий сортировку слиянием C++

Question

Привет я пытаюсь реализовать сортировку слиянием на вектор, который я передаю в функцию. Вот мой код, он не сортирует список, но я не уверен, что не так. Когда я вывожу исходный вектор и отсортированный вектор, между ними есть некоторые различия, но он все еще не отсортирован.

void BestFit::findBest(){
    vector<double> distances;
    vector<double> sorted;
    distances = getDistance(0);
    printDistance(distances);
    sorted = sortDistance(distances);
    printDistance(sorted);
}

vector<double> BestFit::sortDistance(vector<double> distances){
    int mid = distances.size()/2;
    vector<double> left;
    vector<double> right;

    if(distances.size() > 1){
        for(int i = 0; i < mid; i++){
            left.push_back(distances[i]);
        }

        for(int i = mid; i < distances.size(); i++){
            right.push_back(distances[i]);
        }
        return sortDistanceHelp(left, right);
    }else{
        return distances;
    }
}

vector<double> BestFit::sortDistanceHelp(vector<double> left, vector<double> right){
    vector<double> result;
    if(left.size() > 1){
        left = sortDistance(left);
    }else if(right.size() > 1){
        right = sortDistance(right);
    }

    int count = 0;
    int left_count = 0;
    int right_count = 0;
    while(count < (left.size() + right.size())){
        if(left_count < left.size() && right_count < right.size()){
            if(left[left_count] <= right[right_count]){
                result.push_back(left[left_count]);
                left_count++;
            }else{
                result.push_back(right[right_count]);
                right_count++;
            }
        }else if(left_count < left.size()){
            result.push_back(left[left_count]);
            left_count++;
        }else{
            result.push_back(right[right_count]);
            right_count++;
        }
        count++;
    }

    return result;
}

Вот вывод несортированных и отсортированных векторов расстояний.

Unsorted:

Расстояние: 0.679371 Расстояние: 1.263918 Расстояние: 1.575268 Расстояние: 0.117904 Расстояние: 3.851347 Расстояние: 2.317885 Расстояние: 0.899686 Расстояние: 3.916363 Расстояние: 1.513004 Расстояние: 0.446430

Сортировка:

Расстояние: 0.679371 Расстояние: 1.263918 Расстояние: 1.575268 Расстояние: 0.117904 Расстояние: 2.317885 Расстояние: 0.899686 Расстояние: 3.851347 Расстояние: 3.916363 Расстояние: 1.513004 Расстояние: 0.446430

Answer 1

Я уверен, что это проблема. В sortDistanceHelp():

if(left.size() > 1){
    left = sortDistance(left);
}else if(right.size() > 1){ //<<<===== ELSE SHOULD NOT BE HERE
    right = sortDistance(right);
}

Это должно читаться так:

if(left.size() > 1)
    left = sortDistance(left);

if(right.size() > 1)
    right = sortDistance(right);

---

В остальном это простой алгоритм слияния, который вы можете использовать для своих собственных целей с использованием итераторов. Это самый простой алгоритм слияния, который я мог проверить. Он опирается на ваш тип данных для поддержки operator <(), так же как operator =()

template<typename ForwardIterator, typename OutputIterator>
void mergelists
(
    ForwardIterator first1,     // starting iterator of first sequence
    ForwardIterator last1,      // ending iterator of first sequence
    ForwardIterator first2,     // starting iterator of second sequence
    ForwardIterator last2,      // ending iterator of second sequence
    OutputIterator out1)        // output iterator for results
{
    while (first1 != last1 && first2 != last2)
    {
        // note the opposing less-comparison. equtes to (i1 <= i2)
        while (first1 != last1 && !(*first2 < *first1))
            *out1++ = *first1++;

        if (first1 != last1)
        {
            while (first2 != last2 && *first2 < *first1)
                *out1++ = *first2++;
        }
    }

    // doesn't really matter which one finished first
    //  only one of these will put one or more final
    //  nodes into the sequence.
    while (first1 != last1)
        *out1++ = *first1++;
    while (first2 != last2)
        *out1++ = *first2++;
}

В сочетании с общим алгоритмом сортировки слиянием, принимающим начальный итератор и размер, мы имеем:

// general mergesort algorithm
template <typename Iterator>
void mergesort(Iterator first, size_t d)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;

    Iterator last = first + d;
    size_t n = d/2;
    if (n == 0)
        return;

    if (n > 1) // no single elements
        mergesort(first, n);
    if (d > 1) // no single elements
        mergesort(first+n, d-n);

    // merge back into local sequence
    std::vector<value_type> vals;
    vals.reserve(d);
    mergelists(first, first+n, first+n, last, back_inserter(vals));

    // and copy into where it all began
    std::copy(vals.begin(), vals.end(), first);
}

Пример использования этого со случайно заполненным вектором ниже:

int main()
{
    srand((unsigned)time(0));
    vector<int> data;

    // fill a vector with random junk.
    generate_n(back_inserter(data), 20, []() { return std::rand() % 99+1;});
    copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    mergesort(data.begin(), data.size());
    copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}

Пробный прогон I

54 75 14 59 69 18 65 40 52 77 65 43 87 80 99 44 81 40 70 37 
14 18 37 40 40 43 44 52 54 59 65 65 69 70 75 77 80 81 87 99 

Пробный прогон II

53 91 27 29 47 31 20 90 12 18 16 75 61 94 60 55 66 44 35 26 
12 16 18 20 26 27 29 31 35 44 47 53 55 60 61 66 75 90 91 94