2

要素を並べ替えられたベクトルにすばやく挿入することを目的として、C++ プログラムを作成しました。時々機能しますが、常に機能するわけではなく、その理由を理解できませんでした. 紙と鉛筆でアルゴリズムをたどるとうまくいきますが、何かが間違っています。助けてください？

#include <time.h>
#include <cstdlib>
#include <vector>
#include <iostream>
using namespace std;

vector<int> sortedVec;

int main() {
    // Random seed
    srand(time(NULL));

    // Put in n random elements
    for (int i = 0; i < 10; i++) sortedVec.push_back(rand()%10);

    // Sort the vector
    bool swapped = true;
    int endDecrement = 0;
    while (swapped) {
        swapped = false;
        endDecrement++;
        for (int i = 0; i < sortedVec.size()-endDecrement; i++) {
            if (sortedVec.at(i) > sortedVec.at(i+1)) {
                int swap = sortedVec.at(i);
                sortedVec.at(i) = sortedVec.at(i+1);
                sortedVec.at(i+1) = swap;
                swapped = true;
            }
        }
    }

    cout<<"Sorted random list:"<<endl;
    for (int i = 0; i < sortedVec.size(); i++) cout<<sortedVec.at(i)<<endl;

    int toInsert = rand()%10;
    cout<<"Random element to insert = "<<toInsert<<endl;

    // Insert a random int to the sorted vector
    int minIndex = 0;
    int maxIndex = sortedVec.size()-1;
    while (true) {
        int mid = (maxIndex-minIndex)>>1;
        if (toInsert == sortedVec.at(mid) || maxIndex-minIndex < 2) {
            sortedVec.insert(sortedVec.begin()+mid, toInsert);
            break;
        }
        else if (toInsert < sortedVec.at(mid)) maxIndex = mid;
        else if (toInsert > sortedVec.at(mid)) minIndex = mid;
    }

    cout<<"Random list with inserted element:"<<endl;
    for (int i = 0; i < sortedVec.size(); i++) cout<<sortedVec.at(i)<<endl;

    return 0;
}
4

5 に答える 5

2

コメントが指摘しているように、あなたが提案するのは、基本的な問題を解決するためのかなり複雑な方法です。

time(NULL)ランダムジェネレータの初期化を、観察された動作をデバッグする定数に置き換えることで、質問をより魅力的にすることができます。

それがなければ、私は犯人に入札します：

int maxIndex = sortedVec.size()-1;

私はすべきだと思います

int maxIndex = sortedVec.size();

または、最上位の要素を考慮することはありません。

于 2012-10-05T06:09:16.113 に答える
2

コメントに基づいて、次のような構造があると仮定します。

struct data {
    int fval;
    // other stuff we don't care about right now
};

そして、これらのベクトルがあると仮定します。

std::vector<data> items;

新しいアイテムを順番にベクターに挿入したい場合は、バイナリ検索に続いて。を実行する必要はありませstd::insertん。これには、O（log N）検索とそれに続くO（N）挿入が必要です。代わりに、2つを組み合わせることができるため、適切な場所を見つけて挿入を行うために必要なO（N）操作は1つだけです。簡単なバージョンは次のとおりです。

void insert(std::vector<int> &vec, int new_val) { 
    if (vec.empty()) {
        vec.push_back(new_val);
        return;
    }

    vec.resize(vec.size()+1);
    std::vector<int>::reverse_iterator pos = vec.rbegin();

    for ( ; *(pos+1) > new_val && (pos+1) != vec.rend(); ++pos)
        *pos = *(pos+1);
    *pos = new_val;
}

あなたの場合、data構造を挿入して比較したいのです(pos+1)->fval > new_val.fvalが、基本的な考え方はそれ以外はほとんど同じです。実際には、これはおそらく一般的なアルゴリズムとして実装する必要がありますが、現時点では時間がありません。

于 2012-10-05T17:29:08.860 に答える
1

標準ライブラリには、並べ替えのための機能があります。

#include <algorithm>
#include <vector>

template <typename T, typename A, typename C>
class SortedVector {
public:
    SortedVector() {}

    // Initialization
    template <typename It>
    SortedVector(It begin, It end): _data(begin, end) {
        std::sort(_data.begin(), _data.end(), _comparator);

        // if we wanted unicity
        _data.erase(std::unique(_data.begin(), _data.end(), _comparator), _data.end());
    }

    // Addition of element (without checking for unicity)
    void add(T const& element) {
        _data.push_back(element);
        std::inplace_merge(_data.begin(), prev(_data.end()), _data.end(), _comparator);
        // or simply: std::sort(_data.begin(), _data.end(), _comparator);
        // it is surprisingly efficient actually because most sort implementations
        // account for partially sorted range. It is not, however, stable.
    }

    // Addition of element with unicity check
    bool add(T const& element) {
        typename std::vector<T, A>::iterator it =
            std::lower_bound(_data.begin(), _data.end(), element, _comparator);
        if (it != _data.end() and not _comparator(element, *it)) {
            return false;
        }
        size_t const n = it - _data.begin();

        _data.push_back(element);
        std::copy(_data.begin() + n, _data.end() - 1, _data.begin() + n + 1);
        // C++11: std::move
        _data[n] = element;
    }

private:
    std::vector<T, A> _data;
    C _comparator;
};
于 2012-10-05T07:00:36.587 に答える
0

要素を並べ替えられたベクトルにすばやく挿入することを目的として、C++ プログラムを作成しました。

あなたはそれをすべきではありませんでした。std::vector は、カスタム位置への迅速な挿入には適していません。編集：ところで、挿入ではなく交換を行っています。そのため、ベクターの使用は問題ありません。

また、コードは標準関数を使用していないことに苦しんでいます。std::sort、要素を手動で交換したい場合は std::swap もあります。

これも不要です：

int mid = (maxIndex-minIndex)>>1;

コンパイラは、/2 を >>1 に簡単に最適化できます。

編集：

コードが壊れています。これで理由がわかると思います: http://ideone.com/pV5oW

于 2012-10-05T11:21:26.867 に答える
0

私はそれを変更しましたが、今ではすべての場合で機能することを確信しています:

if (toInsert < sortedVec.at(0)) sortedVec.insert(sortedVec.begin(), toInsert);
else if (toInsert > sortedVec.at(sortedVec.size()-1)) sortedVec.push_back(toInsert);
else {  
    int minIndex = 0;
    int maxIndex = sortedVec.size();
    while (true) {
        int mid = (maxIndex+minIndex)>>1;
        if (toInsert == sortedVec.at(mid) || maxIndex-minIndex < 2) {
            sortedVec.insert(sortedVec.begin()+mid+1, toInsert);
            break;
        }
        else if (toInsert < sortedVec.at(mid)) maxIndex = mid;
        else if (toInsert > sortedVec.at(mid)) minIndex = mid;
    }
}

@LeGEC と @chac、私が投稿したアルゴリズムを調べてくれてありがとう、とても役に立ちました。@Jerry Coffin、私は std::upper_bound をこれで動作させましたが、Node クラスの変数では動作しませんでした。

于 2012-10-05T22:39:33.807 に答える