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

未ソート部分の中から最小の要素を見つけ出し、それを未ソート部分の先頭要素と交換していくことでソートをおこなうアルゴリズム。
最良・最悪・平均計算量ともに $O(n^2)$。

【選択ソートの実装例】

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

配列である程度間隔が離れた要素同士で挿入ソートをおこない、徐々に間隔を狭めていくことでソートをおこなうアルゴリズム。
挿入ソートはほとんど整列された配列に対しては高速に動作するといった考え方を用い、大まかにソートしていく。

間隔が 1 のときは、挿入ソートと同じ。
ドナルド・シェルによって考案されたのが名前の由来。
計算量は間隔の取り方によって異なる。

【シェルソートの実装例】

int[] A = {3, 1, 4, 5, 2};
int n = A.length;
int h = 1;
while (h < n / 2) {
  h *= 2;  // 間隔を 2 の累乗で増やす
}
while (h > 0) {
  for (int startIndex = 0; startIndex < h; startIndex++) {
    for (int i = startIndex + h; i < n; i += h) {
      int key = A[i];
      int j = i - h;
      while (j >= 0 && A[j] > key) {
        A[j + h] = A[j];
        j -= h;
      }
      A[j + h] = key;
    }
  }
  h /= 2;  // 間隔を半分にする
}

ヒープを用いてソートをおこなう。
最良・最悪・平均計算量ともに $O(n \log n)$。

【ヒープソートの実装例】

int[] A = {3, 1, 4, 5, 2};
int n = A.length;
heapify(A, n);  // A をヒープに変換
for (int i = n - 1; i > 0; i--) {
  // A[0] (最大値) と A[i] を交換
  int temp = A[0];
  A[0] = A[i];
  A[i] = temp;
  // ヒープの性質を保つために再構築
  heapifyDown(A, 0, i);
}

マージソート同様、分割統治法を用いたソートアルゴリズム。
配列の中から基準となる要素「ピボット」を選び、その要素より小さいものと大きいものに分割して、それぞれの部分配列に対して再帰的にクイックソートを適用していく。

最良・平均計算量は $O(n \log n)$、最悪計算量は $O(n^2)$。
ほかのソートアルゴリズムと比べて、平均的には最も高速だと言われている。

【クイックソートの実装例】

void quickSort(int[] A, int left, int right) {
  if (left >= right) { return; }
  // ピボットを選ぶ
  // ここでは配列の末尾をピボットとする
  int pivot = A[right];
  // pivot 未満の要素が格納されるインデックス
  int i = left - 1;
  for (int j = left; j < right; j++) {
    if (A[j] < pivot) {
      i++;
      // A[i] と A[j] を交換
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
  }
  // ピボットを正しい位置に移動する
  // A[i + 1] は pivot より大きい最小の要素なので、これとピボットを交換すれば OK
  int temp = A[i + 1];
  A[i + 1] = A[right];
  A[right] = temp;

  // 再帰的に左側と右側をソート
  // i + 1 はピボットの位置なので、そこは含めなくてよい
  quickSort(A, left, i);
  quickSort(A, i + 2, right);
}

int[] A = {3, 1, 4, 5, 2};
int n = A.length;
quickSort(A, 0, n - 1);

クイックソートの最悪計算量を回避するために考案されたアルゴリズム。
クイックソートとヒープソート、そして挿入ソートを組み合わせたアルゴリズムで、クイックソートの平均的な高速性とヒープソートの最悪計算量 $O(n \log n)$ を兼ね備えている。