カウントソート

1. カウントソートアルゴリズム
2. カウントソートの例
3. カウントソートアルゴリズムの実装
4. 数え並べ替えアルゴリズムの複雑さ

カウントソートは、非比較ソートアルゴリズムです。各ユニークな要素の出現をカウントすることで配列をソートします。一意な要素のカウントを部分的にハッシュ化し、最終的にソートされた配列の各要素のインデックスを見つけるために計算を行います。非常に高速なアルゴリズムですが、大規模なデータセットには不向きです．[radix sort](/ja/tutorial/algorithm/radix-sort/内のサブルーチンとして使用されます。

カウントソートアルゴリズム

ここでは、n 個の要素を含むソートされていない配列 A[] があるとします。

カウントソートの例

配列があるとしましょう。(6, 3, 2, 7, 4, 5, 4, 2). これをカウントソートアルゴリズムを用いてソートします。

• maxm = 7
• minm = 2
• 範囲 range = 6
• count と output は 0 で初期化されています。

• すべての要素のカウントを計算した後に count 配列を作成します。

• 要素の合計を累積した後の count 配列。

• 最初の繰り返し: A[7]=2.

• 2 回目の反復: A[6]=4.

• 3 回目の反復: A[5]=5.

• 第 4 反復: A[4]=4.

• 第 5 反復: A[3]=7.

• 第 6 反復: A[2]=2.

• 7 回目の反復: A[1]=3.

• 8 回目の反復: A[0]=6.

最後に、配列 output を A 内に格納し、ソートされた配列 2, 2, 3, 4, 4, 5, 6, 7 を取得します。

カウントソートアルゴリズムの実装

#include <iostream>
using namespace std;
const int N = 10;

int maxm(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

int minm(int arr[], int n) {
  int min = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

void countingSort(int arr[], int n) {
  int min = minm(arr, n);
  int max = maxm(arr, n);
  int range = max - min + 1;
  int count[range] = {};
  int output[n];
  for (int i = 0; i < n; i++) count[arr[i] - min]++;

  for (int i = 1; i < range; i++) count[i] += count[i - 1];

  for (int i = n - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
  }

  for (int i = 0; i < n; i++) arr[i] = output[i];
}

int main() {
  int n = 7;
  int arr[7] = {3, 5, 1, 1, 4, 2, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  countingSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

この実装は負の数に対しても動作します。

数え並べ替えアルゴリズムの複雑さ

時間計算量

• 平均ケース

カウントソートは、n のすべての項目を 2 回処理し、count の配列を 1 回処理します。したがって、時間的複雑度は O(n + b) であり、b は入力の範囲です。b は小さいことが多いので、カウントソートの時間的複雑さは [Big Theta]: O(n) のオーダーと言われています。

• 最悪の場合

最悪の場合の時間的複雑さは [Big O]: O(n) です。

• 最悪の場合

最良の時間複雑度は[ビッグオメガ]: O(n) です。これは最悪の時間複雑度と同じです。

空間計算量

カウントソートアルゴリズムの空間複雑度は O(n+b) であり、b は入力の範囲です。これは count と output の配列から来ています。ときには b が n よりも大きくなることもあるが、b が小さい場合、時間的複雑さは O(n) となると言われています。