1

オブジェクト属性の 1 つに基づいてオブジェクトのベクトルをソートしようとしています。各オブジェクトには、整数値が関連付けられています。バブルソートを使用して配列を降順でソートしようとしていますが、何もしていないようです。これが私が試したことです：

void Database::sort (vector<Play*> &vec) {
  for (int i = 0; i < (vec.size() - 1); i++) {
    if (vec.at(i)->getRelevance() < vec.at((i + 1))->getRelevance()) {
      Play *tempObj = new Play(vec.at(i));
      vec.at(i) = vec.at((i +1));
      vec.at((i + 1)) = tempObj;
    }
  }
}

getRelevance() は、オブジェクトをソートするための属性です。

4

1 に答える 1

4

コードの問題の 1 つは、ループが 1 つしかないことです。バブル ソートを実行する場合は、ネストされた 2 つのループが必要です。たとえば、これはおそらくうまくいくでしょう：

void Database::sort (vector<Play*> &vec) {
    bool have_swapped = true;
    for (unsigned j = 1; have_swapped && j < vec.size(); ++j) {
        have_swapped = false;
        for (unsigned i = 0; i < vec.size() - j; ++i) {
            if (vec[i]->getRelevance() < vec[i + 1]->getRelevance()) {
                have_swapped = true;
                Play * tempObj = vec[i];  // Just use:
                vec[i] = vec[i + 1];      //    std::swap(vec[i], vec[i + 1]);
                vec[i + 1] = tempObj;     // instead of these three lines.
            }
        }
    }
}

外側のループが見えますか？それには2つの用途があります。1 つ目は、順序が狂っている要素 (アルゴリズムの教科書では反転と呼ばれていると思います) が残っている間にも、実際にベクトルをくまなく調べていることを保証することです。 " 前の内部ループ反復の結果として、ベクトルの最後に。

ただし、バブル ソートは適切なアルゴリズムではありません (入力データがほぼソートされていることが確実な場合を除きます。この場合、バブル ソートは非常に効率的です)。代わりに、次のようなことができます。

std::sort (vec.begin(), vec.end(),
    [](Play * a, Play * b){return b->getRelevance() < a->getRelevance();}
);

そして、それはほとんどそれです。

いくつかのメモ:

  • を含める必要があります<algorithm>。
  • 関数の 3 番目のパラメーターとしてのことは、「ラムダ」と呼ばれます。ラムダは基本的に名前のない関数であり、コードの途中で記述して渡すことができます。これらはコンピューティングとプログラミングの重要な概念であるため (使用する言語に関係なく)、よく読んでおくことをお勧めします。
  • 項目を関連性の降順で並べ替え、std::sortデフォルトで昇順 (?) に並べ替えるため、bの関連性が の関連性よりも小さい場合、ラムダは true を返しますa。
  • 標準の並べ替えアルゴリズムを使用すると、手動で作成したコードよりも短くて便利であり、正しい可能性がはるかに高くなるだけでなく、一般的に非常に優れたパフォーマンスが得られます (アルゴリズムの Big-O パフォーマンスと実装の両方で)。確かに、バブルソートの方がはるかに優れています (一般的なケースでは)。
于 2013-09-16T23:25:38.900 に答える