C++で実装する初等的ソートアルゴリズム2【バブルソート】

初等的ソートアルゴリズム第2弾。
今回はやたらと耳にすることが多いバブルソートです。

目標

バブルソートを理解する。実際に問題を解いてみます。

バブルソート

数列を昇順にソートします。計算量は $O(N^2)$ です。

アルゴリズム

昇順になっていない隣接要素がなくなるまで、以下を繰り返す：

隣接する要素を末尾から端から比べていき、大小が逆ならば交換

問題を解いてみる

Aizu Online Judge の問題を解いて実装をやってみます。言語はC++です。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A

#include<iostream>
using namespace std;

int main() {
  int i, N, tmp, change=0;
  int seq[100];
  bool flag;  // 交換すべき隣接要素が存在するか？

  cin >> N;
  for (i = 0; i < N; i++) cin >> seq[i];

  // sort
  flag = 1;
  while (flag) {
    flag = 0;
    for (i = N-1; i > 0; i--) {
      if (seq[i] < seq[i-1]) {
        tmp = seq[i];
        seq[i] = seq[i-1];
        seq[i-1] = tmp;
        change++;
        flag = 1;
      }
    }
  }

  for (i = 0; i < N; i++) {
    if (i > 0) cout << " ";
    cout << seq[i];
  }
  cout << endl;
  cout << change << endl;

  return 0;
}