C++ で選択ソートアルゴリズムを実装する

胡金庫 2023年10月12日
C++ で選択ソートアルゴリズムを実装する

この記事では、C++ で選択ソートアルゴリズムを実装する方法について説明します。

C++ で std::vector コンテナの選択ソートを実装する

単純なソートアルゴリズムの中で、選択ソートは実装が最も簡単なものの 1つと見なすことができます。ただし、O(n2)の複雑さがあり、大きなベクトルではまったく非効率になります。

選択ソートは、次のルーチンとして指定できます。最初に、ベクトルで最小値を見つけ、それを最初の要素と交換します。次に、ポインターを 2 番目の要素に移動し、残りのサブベクトルから最小値を見つけて、2 番目の要素と交換します。ポインターを一度に 1 要素ずつ進めながら、ベクトルの残りの部分について前の手順を続けます。

選択ソートの別の説明は、入力ベクトルを 2つの部分に分割することを言うかもしれません L:最初はソートされたサブベクトルで、2 番目はソートされていない要素の残りのサブベクトルです(元の順序です)。ソートされたサブベクトルは指定されたベクトルに存在すると想定できないため、ソートされたサブベクトルとソートされていないサブベクトルの間の除数として最初の要素を選択する必要があります。したがって、最小値を開始位置の要素と交換し始めると。ベクトルは自然にソートされた部分とソートされていない部分に分割されます。

次の例では、std::vector オブジェクトへの参照を取得し、要素のインプレース変更を実行する selectionSort 関数を実装します。std::min_element アルゴリズムを利用して、各反復の最小値を見つけました。これは、初めてアルゴリズムをよりよく理解するのに役立ちます。

C
++ cCopy#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void selectionSort(vector<T> &vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::swap(*it, *std::min_element(it, vec.end()));
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  selectionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

出力:

 textCopy43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;

または、selectionSort 関数を 2 番目の for ループで書き直して、各反復の残りのソートされていないサブベクトルの最小値を求めることもできます。このバージョンは、アルゴリズムの複雑さの分析に適しています。選択ソートアルゴリズムの実行時間は 2 次ですが、マージソートやヒープソートなどの O(n log n)アルゴリズムと比較して、小さいベクトルでは驚くほど効率的です。この場合は一定時間の操作である 1つの STL 関数 std::swap を引き続き使用していることに注意してください。コード例を簡潔にすると便利です。

C
++ cCopy#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void selectionSort(vector<T> &vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    auto min = it;

    for (auto i = it + 1; i != vec.end(); ++i) {
      if (*i < *min) min = i;
    }

    std::swap(*it, *min);
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  selectionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

出力:

 textCopy43; 5; 123; 94; 359; -23; 2; -1; 
-23; -1; 2; 5; 43; 94; 123; 359; 
著者: 胡金庫
胡金庫 avatar 胡金庫 avatar

DelftStack.comの創設者です。Jinku はロボティクスと自動車産業で8年以上働いています。自動テスト、リモートサーバーからのデータ収集、耐久テストからのレポート作成が必要となったとき、彼はコーディングスキルを磨きました。彼は電気/電子工学のバックグラウンドを持っていますが、組み込みエレクトロニクス、組み込みプログラミング、フロントエンド/バックエンドプログラミングへの関心を広げています。

LinkedIn Facebook

関連記事 - C++ Algorithm