バブルソートを理解する

前回に引き続き今回はバブルソートについてです

バブルソートって？

ソートアルゴリズムの1つで、処理時間が遅いものとなります
詳しくは以下のサイトが図解で分かりやすく記載されています

バブルソートを実装する

ランダム配列は前回の記事で作成したものを使用します。それでは実際にバブルソートをC＋＋で実装してみます

template <typename T>
void bubbleSort(std::vector<T>& arr, int size) {

    for (int i = 0; i < size - 1; i++) {
        for (int k = 0; k < size - i - 1; k++) {
            // 隣り合った要素を比較し、順序が逆であれば交換
            if (arr[k] > arr[k + 1]) {
                std::swap(arr[k], arr[k + 1]);
            }
        }
    }
}

前回のクイックソートと比べるとシンプルなものとなります

実際に動かしてみる

検証用の配列を作成し、それをバブルソートで並び替えて結果を見てみましょう

std::vector<int> arr = RandomCreate();
int size = arr.size();

std::cout << "Original Array: ";
for (int i : arr) {
    std::cout << i << " ";
}
std::cout << std::endl;


bubbleSort(arr, size);

std::cout << "Sorted Array: ";
for (int i : arr) {
    std::cout << i << " ";
}
std::cout << std::endl;

バブルソートを用いて配列が並び変えられていることが確認できました