関数とループ不変条件

正しく設計された関数は、関数の実行前の状態の条件と実行後の状態の条件が定められています。

挿入ソートにおける挿入処理を考えてみます。 今、配列 $a$ の先頭 $k - 1 (k > 0)$ 個がソート済みであり、$a$ の $k$ 番目の要素を適切な位置に移動することで、 $a$ の先頭 $k$ 個が昇順にソート済みとなるようにします。 この処理を 関数 $\text{insert}(data, k)$ とします。 関数実行前には「$0 < k \leq |a|$ かつ $a$ の先頭 $k - 1$ 個が昇順にソート済み」という条件を満たす必要があります。 また、関数実行後には「$a$ の先頭 $k$ 個の要素が昇順にソート済み」という条件を満たす必要があります。 関数実行前と実行後の条件を満たすようにこの関数を実装すると以下のようになります。

void insert(int[] a, int k) {
  // a の先頭 k - 1 個がソート済み
  for (int i = k; i >= 1 && a[i] < a[i - 1]; --i) {
    // a の0番目からi - 1 番目までがソート済み かつ i + 1番目からk 番目までがソート済み
    swap(a, i, i - 1);
    // a の0番目からi - 2 番目までがソート済み かつ i 番目からk 番目までがソート済み
  }
  // a の先頭 k 個がソート済み
}

void swap(int[] data, int i, int j) {
  int tmp = data[i];
  data[i] = data[j];
  data[j] = tmp;
}

これを用いると挿入ソートは以下のように実装することができます。

void insertionSort(int[] a) {
  for (int k = 0; k < a.length; ++k) {
    // a の先頭 k - 1 個がソート済み
    insert(a, i);
    // a の先頭 k 個がソート済み
  }
}

以上のようにループを行うと、ループを抜けた後に「a の先頭 a.length 個がソート済み」という条件が満たされ、a のソートが行えます。

関数の実行前と実行後が満たしている条件のように、プログラムのある時点で満たしているべき条件を 不変条件 と呼びます。 不変条件は、関数の実行前後以外にも、ループの途中やプログラムの任意の部分で考えることができます。 挿入ソートは、不変条件を考えることでinsert(a, k) を用いなくても以下のように実装することができます。

void insertionSort(int[] a) {
  for (int k = 0; k < a.length; ++k) {
    // a の先頭 k - 1 個がソート済み
    for (int i = k; i >= 1 && a[i] < a[i - 1]; --i) {
      swap(a, i, i - 1);
    }
    // a の先頭 k 個がソート済み
  }
}

不変条件を意識することで、再帰関数やループを用いた処理を適切に実装できるようになるでしょう。