【就プロ】バブルソート

はじめに

今回はソートの一回目です。
ソートとは、大小関係が考えることができる要素の集合に対して、昇順（または降順）に並び替えることをいう。
今回はソートの中でも最も簡単なソートアルゴリズムであるバブルソートについて説明します。

バブルソート

まず長さ$n$の配列$a$が昇順にソートされているのかを確認するためには、どうするかを考えてみる。昇順であることは「隣り合う二つの要素が昇順に並んでいる」ことを確かめることで確認できる。したがって、$O(n)$で確認可能である。

このソートの確かめ方を利用したのが、バブルソートです。
バブルソートは「隣り合う二つの要素を比較し、昇順でなければ順番を入れ替える」という操作を繰り返します。
このようにすることで、配列の中で最大の要素が次々と後ろに移動していくような形になります。
このように最大の要素が泡のように浮き出てくることから、バブルソートと呼ばれます。

C++

#include<iostream>

using namespace std;

bool compare(const int a, const int b) {
    return a < b;
}

void bubble_sort(int* arr, int len) {
    for (int i = len - 1; i >= 0; i--) {
	bool bSort = true;
	for (int j = 0; j < i; ++j) {
            // もしソートされていない場合は入れ替え                
	    if (!compare(arr[j], arr[j + 1])) {
		int buf = arr[j + 1];
		arr[j + 1] = arr[j];
		arr[j] = buf;
		bSort = false;
	    }
	}

        // すべてソート済みであれば終了
        if (bSort) return;
    }
}

int N;
int* A;

int main(int argc, char* argv[]) {
    cin >> N;
    A = new int[N];
    for (int i = 0; i < N; i++) {
	cin >> A[i];
    }

    bubble_sort(A, N);

    for (int i = 0; i < N; i++) {
	cout << A[i] << " ";
    }
    cout << endl;

    return 0;
}