C++ のバブルソートアルゴリズム
この記事では、C++ でバブルソートアルゴリズムを実装する方法のいくつかの方法について説明します。
std::vector コンテナのバブルソートを実装する
バブルソートは、最も単純なソートアルゴリズムの 1つです。隣接する各ペアを比較するオブジェクトのリストを繰り返し処理し、順序付けされていない場合は、要素が交換されます。要素の読み取りは比較式を使用してのみ行われるため、比較ソートアルゴリズムとして分類されます。次のサンプルコードでは、一般的なベクトルオブジェクトを処理するためにバブルソートを実装しています。ソートルーチン全体を定義するには、bubbleSort という名前の単一の関数で十分です。関数はテンプレート化されており、唯一の引数としてベクトルへの参照を取ります。
bubbleSort には、昇順で並べ替えられるまで vector 要素を反復処理する 2つのネストされた for ループが含まれています。外側の for ループの各反復は、1つの要素を正しい場所に格納することに注意してください。後者の要素はベクトルの最後に格納され、内側のループを通過するベクトルの部分で最大の要素になります。実装を簡素化し、読みやすくするために、std::swap アルゴリズムを利用したことに注意してください。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void bubbleSort(vector<T> &vec) {
for (size_t i = 0; i < vec.size() - 1; ++i) {
for (size_t j = 0; j < vec.size() - i - 1; ++j) {
if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
}
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
bubbleSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
出力：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
経験的なタイミング測定でバブルソートの複雑さを分析する
バブルソートは、2 次実行時クラスに属します。実際、このアルゴリズムの平均時間と最悪の場合のパフォーマンスはどちらも 2 次式です-O（n2）。したがって、この方法は、大きな入力データセットに対してはまったく非効率的になります。このため、実際には使用されていません。たとえば、入力ベクトルの長さを 10 増やすと、実行時間はおよそ 100 倍になります。ただし、入力ベクトルの要素が 1 か所だけ順序が狂っている特殊なケース（1032547698 シーケンスなど）では、バブルソートが非常に効率的である可能性があることに注意してください。後者の場合、アルゴリズムの複雑さは線形になります。次のコード例は、gettimeofday 関数を使用して 2つの異なるベクトルの実行時間を測定し、その結果をコンソールに出力します。
#include <sys/time.h>
#include <algorithm>
#include <ctime>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void bubbleSort(vector<T> &vec) {
for (size_t i = 0; i < vec.size() - 1; ++i) {
for (size_t j = 0; j < vec.size() - i - 1; ++j) {
if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
}
}
}
float time_diff(struct timeval *start, struct timeval *end) {
return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}
int main() {
struct timeval start {};
struct timeval end {};
vector<int> vec3(100, 10);
vector<int> vec4(1000, 10);
gettimeofday(&start, nullptr);
bubbleSort(vec3);
gettimeofday(&end, nullptr);
printf("bubbleSort %zu elements: %0.8f sec\n", vec3.size(),
time_diff(&start, &end));
gettimeofday(&start, nullptr);
bubbleSort(vec4);
gettimeofday(&end, nullptr);
printf("bubbleSort %zu elements: %0.8f sec\n", vec4.size(),
time_diff(&start, &end));
return EXIT_SUCCESS;
}
出力：
bubbleSort 100 elements: 0.00002500 sec
bubbleSort 1000 elements: 0.00184900 sec
