テクノロジー編26: アルゴリズム

隣り合う要素を比較して、前の要素が後ろの要素より大きければ交換することを繰り返すソートアルゴリズム。

平均・最悪計算量は O(n^2)、最良計算量は O(n)。

int[] A = {3, 1, 4, 5, 2};
int n = A.length;
for (int i = 0; i < n - 1; i++) {
  boolean swapped = false;
  for (int j = 0; j < n - i - 1; j++) {
    if (A[j] > A[j + 1]) {
      swapped = true;
      // A[j] と A[j + 1] を交換
      int temp = A[j];
      A[j] = A[j + 1];
      A[j + 1] = temp;
    }
  }
  if (!swapped) {
    break;
  }
}

未ソート部分の要素をソート済み部分の適切な位置に挿入していくことでソートをおこなうアルゴリズム。
平均・最悪計算量は O(n^2)、最良計算量は O(n)。

int[] A = {3, 1, 4, 5, 2};
int n = A.length;
for (int i = 1; i < n; i++) {
  int key = A[i];
  int j = i - 1;
  while (j >= 0 && A[j] > key) {
    A[j + 1] = A[j];
    j--;
  }
  A[j + 1] = key;
}

配列を分割し、分割した配列を再帰的にソートし、そのソート済み部分を統合していくことでソートをおこなう。
分割統治法 (大きなものを小さく分割し、それに対して処理をおこない、統合していく方法) の一種。
よく再帰的な関数を使って実装される。

2 分割にした場合のマージソートは、最良・平均・最悪計算量ともに O(n log n) 。

ArrayList<Integer> mergeSort(ArrayList<Integer> A) {
  // A が空または要素が 1 つ以下の場合はそのまま返す
  if (A.size() <= 1) {
    return A;
  }

  // A を 2 分割する
  int mid = A.size() / 2;
  ArrayList<Integer> left = new ArrayList<>(A.subList(0, mid));
  ArrayList<Integer> right = new ArrayList<>(A.subList(mid, A.size()));

  // 左右の配列を再帰的にソートする
  left = mergeSort(left);
  right = mergeSort(right);

  // 統合していく
  ArrayList<Integer> merged = new ArrayList<>();
  int i = 0, j = 0;
  // 両方の配列を走査しながら、要素を比較して小さい方を追加していく
  while (i < left.size() && j < right.size()) {
    if (left.get(i) <= right.get(j)) {
      merged.add(left.get(i));
      i++;
    } else {
      merged.add(right.get(j));
      j++;
    }
  }
  // 余った要素を追加する
  while (i < left.size()) {
    merged.add(left.get(i));
    i++;
  }
  while (j < right.size()) {
    merged.add(right.get(j));
    j++;
  }
  // 統合した配列を返す
  return merged;
}