1

こんにちは、関数に渡すベクトルにマージソートを実装しようとしています。これが私のコードです。リストはソートされませんが、何が問題なのかわかりません。元のベクトルと並べ替えられたベクトルを出力すると、2 つの間にいくつかの違いがありますが、まだ並べ替えられていません。

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;
}

以下は、ソートされていない距離ベクトルとソートされた距離ベクトルの出力です。

未分類:

距離: 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

4

1 に答える 1

0

これが問題だと確信しています。で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
于 2013-03-09T06:27:04.880 に答える