コンテンツにスキップ
日本語版のレビュアーを募集しています。詳しくは こちら をご覧ください。

# 11.9 計数ソート

計数ソート（counting sort）は要素数を集計することでソートを実現し、通常は整数配列に適用されます。

## 11.9.1 単純な実装

まず簡単な例を見てみましょう。長さ \(n\) の配列 `nums` が与えられ、その要素はすべて「非負整数」であるとします。計数ソートの全体的な流れを以下の図に示します。

1. 配列を走査し、その中の最大値を見つけて \(m\) とし、続いて長さ \(m + 1\) の補助配列 `counter` を作成します。
2. `counter` を用いて `nums` 内の各数値の出現回数を集計します。ここで `counter[num]` は数値 `num` の出現回数に対応します。集計方法は非常に簡単で、`nums` を走査し（現在の数値を `num` とする）、各回で `counter[num]` を \(1\) 増やせばよいです。
3. `counter` の各インデックスは自然に順序づけられているため、すべての数値はすでに整列された状態とみなせます。続いて `counter` を走査し、各数値の出現回数に応じて小さい順に `nums` へ書き戻せば完了です。

図 11-16 計数ソートの流れ

コードは以下のとおりです：

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
counting_sort.py

    def counting_sort_naive(nums: list[int]):
        """計数ソート"""
        # 簡易版。オブジェクトのソートには使えない
        # 1. 配列の最大要素 m を求める
        m = max(nums)
        # 2. 各数値の出現回数を数える
        # counter[num] は num の出現回数を表す
        counter = [0] * (m + 1)
        for num in nums:
            counter[num] += 1
        # 3. counter を走査し、各要素を元の配列 nums に書き戻す
        i = 0
        for num in range(m + 1):
            for _ in range(counter[num]):
                nums[i] = num
                i += 1

counting_sort.cpp

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    void countingSortNaive(vector<int> &nums) {
        // 1. 配列の最大要素 m を求める
        int m = 0;
        for (int num : nums) {
            m = max(m, num);
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        vector<int> counter(m + 1, 0);
        for (int num : nums) {
            counter[num]++;
        }
        // 3. counter を走査し、各要素を元の配列 nums に書き戻す
        int i = 0;
        for (int num = 0; num < m + 1; num++) {
            for (int j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
    }

counting_sort.java

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    void countingSortNaive(int[] nums) {
        // 1. 配列の最大要素 m を求める
        int m = 0;
        for (int num : nums) {
            m = Math.max(m, num);
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        int[] counter = new int[m + 1];
        for (int num : nums) {
            counter[num]++;
        }
        // 3. counter を走査し、各要素を元の配列 nums に書き戻す
        int i = 0;
        for (int num = 0; num < m + 1; num++) {
            for (int j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
    }

counting_sort.cs

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    void CountingSortNaive(int[] nums) {
        // 1. 配列の最大要素 m を求める
        int m = 0;
        foreach (int num in nums) {
            m = Math.Max(m, num);
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        int[] counter = new int[m + 1];
        foreach (int num in nums) {
            counter[num]++;
        }
        // 3. counter を走査し、各要素を元の配列 nums に書き戻す
        int i = 0;
        for (int num = 0; num < m + 1; num++) {
            for (int j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
    }

counting_sort.go

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    func countingSortNaive(nums []int) {
        // 1. 配列の最大要素 m を求める
        m := 0
        for _, num := range nums {
            if num > m {
                m = num
            }
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        counter := make([]int, m+1)
        for _, num := range nums {
            counter[num]++
        }
        // 3. counter を走査し、各要素を元の配列 nums に書き戻す
        for i, num := 0, 0; num < m+1; num++ {
            for j := 0; j < counter[num]; j++ {
                nums[i] = num
                i++
            }
        }
    }

counting_sort.swift

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    func countingSortNaive(nums: inout [Int]) {
        // 1. 配列の最大要素 m を求める
        let m = nums.max()!
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        var counter = Array(repeating: 0, count: m + 1)
        for num in nums {
            counter[num] += 1
        }
        // 3. counter を走査し、各要素を元の配列 nums に書き戻す
        var i = 0
        for num in 0 ..< m + 1 {
            for _ in 0 ..< counter[num] {
                nums[i] = num
                i += 1
            }
        }
    }

counting_sort.js

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    function countingSortNaive(nums) {
        // 1. 配列の最大要素 m を求める
        let m = Math.max(...nums);
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        const counter = new Array(m + 1).fill(0);
        for (const num of nums) {
            counter[num]++;
        }
        // 3. counter を走査し、各要素を元の配列 nums に書き戻す
        let i = 0;
        for (let num = 0; num < m + 1; num++) {
            for (let j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
    }

counting_sort.ts

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    function countingSortNaive(nums: number[]): void {
        // 1. 配列の最大要素 m を求める
        let m: number = Math.max(...nums);
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        const counter: number[] = new Array<number>(m + 1).fill(0);
        for (const num of nums) {
            counter[num]++;
        }
        // 3. counter を走査し、各要素を元の配列 nums に書き戻す
        let i = 0;
        for (let num = 0; num < m + 1; num++) {
            for (let j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
    }

counting_sort.dart

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    void countingSortNaive(List<int> nums) {
      // 1. 配列の最大要素 m を求める
      int m = 0;
      for (int _num in nums) {
        m = max(m, _num);
      }
      // 2. 各数値の出現回数を数える
      // counter[_num] は _num の出現回数を表す
      List<int> counter = List.filled(m + 1, 0);
      for (int _num in nums) {
        counter[_num]++;
      }
      // 3. counter を走査し、各要素を元の配列 nums に書き戻す
      int i = 0;
      for (int _num = 0; _num < m + 1; _num++) {
        for (int j = 0; j < counter[_num]; j++, i++) {
          nums[i] = _num;
        }
      }
    }

counting_sort.rs

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    fn counting_sort_naive(nums: &mut [i32]) {
        // 1. 配列の最大要素 m を求める
        let m = *nums.iter().max().unwrap();
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        let mut counter = vec![0; m as usize + 1];
        for &num in nums.iter() {
            counter[num as usize] += 1;
        }
        // 3. counter を走査し、各要素を元の配列 nums に書き戻す
        let mut i = 0;
        for num in 0..m + 1 {
            for _ in 0..counter[num as usize] {
                nums[i] = num;
                i += 1;
            }
        }
    }

counting_sort.c

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    void countingSortNaive(int nums[], int size) {
        // 1. 配列の最大要素 m を求める
        int m = 0;
        for (int i = 0; i < size; i++) {
            if (nums[i] > m) {
                m = nums[i];
            }
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        int *counter = calloc(m + 1, sizeof(int));
        for (int i = 0; i < size; i++) {
            counter[nums[i]]++;
        }
        // 3. counter を走査し、各要素を元の配列 nums に書き戻す
        int i = 0;
        for (int num = 0; num < m + 1; num++) {
            for (int j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
        // 4. メモリを解放する
        free(counter);
    }

counting_sort.kt

    /* 計数ソート */
    // 簡易実装のため、オブジェクトのソートには使えない
    fun countingSortNaive(nums: IntArray) {
        // 1. 配列の最大要素 m を求める
        var m = 0
        for (num in nums) {
            m = max(m, num)
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        val counter = IntArray(m + 1)
        for (num in nums) {
            counter[num]++
        }
        // 3. counter を走査し、各要素を元の配列 nums に書き戻す
        var i = 0
        for (num in 0..<m + 1) {
            var j = 0
            while (j < counter[num]) {
                nums[i] = num
                j++
                i++
            }
        }
    }

counting_sort.rb

    ### 計数ソート ###
    def counting_sort_naive(nums)
      # 簡易版。オブジェクトのソートには使えない
      # 1. 配列の最大要素 m を求める
      m = 0
      nums.each { |num| m = [m, num].max }
      # 2. 各数値の出現回数を数える
      # counter[num] は num の出現回数を表す
      counter = Array.new(m + 1, 0)
      nums.each { |num| counter[num] += 1 }
      # 3. counter を走査し、各要素を元の配列 nums に書き戻す
      i = 0
      for num in 0...(m + 1)
        (0...counter[num]).each do
          nums[i] = num
          i += 1
        end
      end
    end

コードの可視化

全画面で見る >

計数ソートとバケットソートの関係

バケットソートの観点から見ると、計数ソートにおける計数配列 `counter` の各インデックスを 1 つのバケットとみなし、個数を数える過程を各要素を対応するバケットへ振り分ける操作とみなせます。本質的には、計数ソートは整数データにおけるバケットソートの特殊な一例です。

## 11.9.2 完全な実装

注意深い読者なら、**入力データがオブジェクトである場合、上記の手順 `3.` は機能しない**ことに気づくかもしれません。入力データが商品オブジェクトであり、商品価格（クラスのメンバ変数）に基づいて商品をソートしたいとします。しかし上記のアルゴリズムが返せるのは価格のソート結果だけです。

では、元のデータのソート結果を得るにはどうすればよいのでしょうか。まず `counter` の「累積和」を計算します。名前のとおり、インデックス `i` における累積和 `prefix[i]` は、配列の先頭から `i` 番目までの要素の総和に等しくなります：

\[ \text{prefix}[i] = \sum_{j=0}^i \text{counter[j]} \]

累積和には明確な意味があり、`prefix[num] - 1` は要素 `num` が結果配列 `res` に最後に現れるインデックスを表します。この情報は非常に重要で、各要素が結果配列のどの位置に現れるべきかを示してくれます。続いて元の配列 `nums` を逆順に走査し、各要素 `num` に対して各反復で次の 2 つの手順を行います。

1. `num` を配列 `res` のインデックス `prefix[num] - 1` に格納します。
2. 累積和 `prefix[num]` を \(1\) 減らし、次に `num` を配置するインデックスを得ます。

走査が完了すると、配列 `res` にソート済みの結果が格納されます。最後に `res` で元の配列 `nums` を上書きすれば完了です。以下の図は完全な計数ソートの流れを示しています。

<1><2><3><4><5><6><7><8>

図 11-17 計数ソートの手順

計数ソートの実装コードは以下のとおりです：

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
counting_sort.py

    def counting_sort(nums: list[int]):
        """計数ソート"""
        # 完全版。オブジェクトをソートでき、かつ安定ソートである
        # 1. 配列の最大要素 m を求める
        m = max(nums)
        # 2. 各数値の出現回数を数える
        # counter[num] は num の出現回数を表す
        counter = [0] * (m + 1)
        for num in nums:
            counter[num] += 1
        # 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        # つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for i in range(m):
            counter[i + 1] += counter[i]
        # 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        # 結果を記録するための配列 res を初期化
        n = len(nums)
        res = [0] * n
        for i in range(n - 1, -1, -1):
            num = nums[i]
            res[counter[num] - 1] = num  # num を対応するインデックスに配置
            counter[num] -= 1  # 累積和を 1 減らして、次に num を配置するインデックスを得る
        # 結果配列 res で元の配列 nums を上書きする
        for i in range(n):
            nums[i] = res[i]

counting_sort.cpp

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    void countingSort(vector<int> &nums) {
        // 1. 配列の最大要素 m を求める
        int m = 0;
        for (int num : nums) {
            m = max(m, num);
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        vector<int> counter(m + 1, 0);
        for (int num : nums) {
            counter[num]++;
        }
        // 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        // つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for (int i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        // 結果を記録するための配列 res を初期化
        int n = nums.size();
        vector<int> res(n);
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            res[counter[num] - 1] = num; // num を対応するインデックスに配置
            counter[num]--;              // 累積和を 1 減らして、次に num を配置するインデックスを得る
        }
        // 結果配列 res で元の配列 nums を上書きする
        nums = res;
    }

counting_sort.java

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    void countingSort(int[] nums) {
        // 1. 配列の最大要素 m を求める
        int m = 0;
        for (int num : nums) {
            m = Math.max(m, num);
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        int[] counter = new int[m + 1];
        for (int num : nums) {
            counter[num]++;
        }
        // 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        // つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for (int i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        // 結果を記録するための配列 res を初期化
        int n = nums.length;
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            res[counter[num] - 1] = num; // num を対応するインデックスに配置
            counter[num]--; // 累積和を 1 減らして、次に num を配置するインデックスを得る
        }
        // 結果配列 res で元の配列 nums を上書きする
        for (int i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

counting_sort.cs

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    void CountingSort(int[] nums) {
        // 1. 配列の最大要素 m を求める
        int m = 0;
        foreach (int num in nums) {
            m = Math.Max(m, num);
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        int[] counter = new int[m + 1];
        foreach (int num in nums) {
            counter[num]++;
        }
        // 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        // つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for (int i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        // 結果を記録するための配列 res を初期化
        int n = nums.Length;
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            res[counter[num] - 1] = num; // num を対応するインデックスに配置
            counter[num]--; // 累積和を 1 減らして、次に num を配置するインデックスを得る
        }
        // 結果配列 res で元の配列 nums を上書きする
        for (int i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

counting_sort.go

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    func countingSort(nums []int) {
        // 1. 配列の最大要素 m を求める
        m := 0
        for _, num := range nums {
            if num > m {
                m = num
            }
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        counter := make([]int, m+1)
        for _, num := range nums {
            counter[num]++
        }
        // 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        // つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for i := 0; i < m; i++ {
            counter[i+1] += counter[i]
        }
        // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        // 結果を記録するための配列 res を初期化
        n := len(nums)
        res := make([]int, n)
        for i := n - 1; i >= 0; i-- {
            num := nums[i]
            // num を対応するインデックスに配置
            res[counter[num]-1] = num
            // 累積和を 1 減らして、次に num を配置するインデックスを得る
            counter[num]--
        }
        // 結果配列 res で元の配列 nums を上書きする
        copy(nums, res)
    }

counting_sort.swift

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    func countingSort(nums: inout [Int]) {
        // 1. 配列の最大要素 m を求める
        let m = nums.max()!
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        var counter = Array(repeating: 0, count: m + 1)
        for num in nums {
            counter[num] += 1
        }
        // 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        // つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for i in 0 ..< m {
            counter[i + 1] += counter[i]
        }
        // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        // 結果を記録するための配列 res を初期化
        var res = Array(repeating: 0, count: nums.count)
        for i in nums.indices.reversed() {
            let num = nums[i]
            res[counter[num] - 1] = num // num を対応するインデックスに配置
            counter[num] -= 1 // 累積和を 1 減らして、次に num を配置するインデックスを得る
        }
        // 結果配列 res で元の配列 nums を上書きする
        for i in nums.indices {
            nums[i] = res[i]
        }
    }

counting_sort.js

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    function countingSort(nums) {
        // 1. 配列の最大要素 m を求める
        let m = Math.max(...nums);
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        const counter = new Array(m + 1).fill(0);
        for (const num of nums) {
            counter[num]++;
        }
        // 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        // つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for (let i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        // 結果を記録するための配列 res を初期化
        const n = nums.length;
        const res = new Array(n);
        for (let i = n - 1; i >= 0; i--) {
            const num = nums[i];
            res[counter[num] - 1] = num; // num を対応するインデックスに配置
            counter[num]--; // 累積和を 1 減らして、次に num を配置するインデックスを得る
        }
        // 結果配列 res で元の配列 nums を上書きする
        for (let i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

counting_sort.ts

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    function countingSort(nums: number[]): void {
        // 1. 配列の最大要素 m を求める
        let m: number = Math.max(...nums);
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        const counter: number[] = new Array<number>(m + 1).fill(0);
        for (const num of nums) {
            counter[num]++;
        }
        // 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        // つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for (let i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        // 結果を記録するための配列 res を初期化
        const n = nums.length;
        const res: number[] = new Array<number>(n);
        for (let i = n - 1; i >= 0; i--) {
            const num = nums[i];
            res[counter[num] - 1] = num; // num を対応するインデックスに配置
            counter[num]--; // 累積和を 1 減らして、次に num を配置するインデックスを得る
        }
        // 結果配列 res で元の配列 nums を上書きする
        for (let i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

counting_sort.dart

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    void countingSort(List<int> nums) {
      // 1. 配列の最大要素 m を求める
      int m = 0;
      for (int _num in nums) {
        m = max(m, _num);
      }
      // 2. 各数値の出現回数を数える
      // counter[_num] は _num の出現回数を表す
      List<int> counter = List.filled(m + 1, 0);
      for (int _num in nums) {
        counter[_num]++;
      }
      // 3. counter の累積和を求め、「出現回数」を「末尾インデックス」に変換する
      // つまり counter[_num]-1 は、res において _num が最後に出現する位置のインデックスである
      for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
      }
      // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
      // 結果を記録するための配列 res を初期化
      int n = nums.length;
      List<int> res = List.filled(n, 0);
      for (int i = n - 1; i >= 0; i--) {
        int _num = nums[i];
        res[counter[_num] - 1] = _num; // _num を対応する添字に配置
        counter[_num]--; // 累積和を 1 減らし、次に _num を配置するインデックスを得る
      }
      // 結果配列 res で元の配列 nums を上書きする
      nums.setAll(0, res);
    }

counting_sort.rs

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    fn counting_sort(nums: &mut [i32]) {
        // 1. 配列の最大要素 m を求める
        let m = *nums.iter().max().unwrap() as usize;
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        let mut counter = vec![0; m + 1];
        for &num in nums.iter() {
            counter[num as usize] += 1;
        }
        // 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        // つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for i in 0..m {
            counter[i + 1] += counter[i];
        }
        // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        // 結果を記録するための配列 res を初期化
        let n = nums.len();
        let mut res = vec![0; n];
        for i in (0..n).rev() {
            let num = nums[i];
            res[counter[num as usize] - 1] = num; // num を対応するインデックスに配置
            counter[num as usize] -= 1; // 累積和を 1 減らして、次に num を配置するインデックスを得る
        }
        // 結果配列 res で元の配列 nums を上書きする
        nums.copy_from_slice(&res)
    }

counting_sort.c

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    void countingSort(int nums[], int size) {
        // 1. 配列の最大要素 m を求める
        int m = 0;
        for (int i = 0; i < size; i++) {
            if (nums[i] > m) {
                m = nums[i];
            }
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        int *counter = calloc(m, sizeof(int));
        for (int i = 0; i < size; i++) {
            counter[nums[i]]++;
        }
        // 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        // つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for (int i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        // 結果を記録するための配列 res を初期化
        int *res = malloc(sizeof(int) * size);
        for (int i = size - 1; i >= 0; i--) {
            int num = nums[i];
            res[counter[num] - 1] = num; // num を対応するインデックスに配置
            counter[num]--;              // 累積和を 1 減らして、次に num を配置するインデックスを得る
        }
        // 結果配列 res で元の配列 nums を上書きする
        memcpy(nums, res, size * sizeof(int));
        // 5. メモリを解放する
        free(res);
        free(counter);
    }

counting_sort.kt

    /* 計数ソート */
    // 完全な実装で、オブジェクトをソートでき、かつ安定ソートである
    fun countingSort(nums: IntArray) {
        // 1. 配列の最大要素 m を求める
        var m = 0
        for (num in nums) {
            m = max(m, num)
        }
        // 2. 各数値の出現回数を数える
        // counter[num] は num の出現回数を表す
        val counter = IntArray(m + 1)
        for (num in nums) {
            counter[num]++
        }
        // 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
        // つまり counter[num]-1 は、num が res に最後に現れるインデックス
        for (i in 0..<m) {
            counter[i + 1] += counter[i]
        }
        // 4. nums を逆順に走査し、各要素を結果配列 res に格納する
        // 結果を記録するための配列 res を初期化
        val n = nums.size
        val res = IntArray(n)
        for (i in n - 1 downTo 0) {
            val num = nums[i]
            res[counter[num] - 1] = num // num を対応するインデックスに配置
            counter[num]-- // 累積和を 1 減らして、次に num を配置するインデックスを得る
        }
        // 結果配列 res で元の配列 nums を上書きする
        for (i in 0..<n) {
            nums[i] = res[i]
        }
    }

counting_sort.rb

    ### 計数ソート ###
    def counting_sort(nums)
      # 完全版。オブジェクトをソートでき、かつ安定ソートである
      # 1. 配列の最大要素 m を求める
      m = nums.max
      # 2. 各数値の出現回数を数える
      # counter[num] は num の出現回数を表す
      counter = Array.new(m + 1, 0)
      nums.each { |num| counter[num] += 1 }
      # 3. counter の累積和を求めて、「出現回数」を「末尾インデックス」に変換する
      # つまり counter[num]-1 は、num が res に最後に現れるインデックス
      (0...m).each { |i| counter[i + 1] += counter[i] }
      # 4. nums を逆順に走査し、各要素を結果配列 res に格納する
      # 結果を記録するための配列 res を初期化する
      n = nums.length
      res = Array.new(n, 0)
      (n - 1).downto(0).each do |i|
        num = nums[i]
        res[counter[num] - 1] = num # num を対応するインデックスに配置
        counter[num] -= 1 # 累積和を 1 減らして、次に num を配置するインデックスを得る
      end
      # 結果配列 res で元の配列 nums を上書きする
      (0...n).each { |i| nums[i] = res[i] }
    end

コードの可視化

全画面で見る >

## 11.9.3 アルゴリズムの特性

- 時間計算量は \(O(n + m)\)、非適応ソート ：`nums` の走査と `counter` の走査が含まれ、いずれも線形時間です。一般には \(n \gg m\) であり、時間計算量は \(O(n)\) に近づきます。
- 空間計算量は \(O(n + m)\)、非インプレースソート：長さがそれぞれ \(n\) と \(m\) の配列 `res` と `counter` を利用します。
- 安定ソート：`res` に要素を埋める順序が「右から左」であるため、`nums` を逆順に走査することで等しい要素どうしの相対位置が変化するのを防ぎ、安定ソートを実現できます。実際には、`nums` を順方向に走査しても正しいソート結果は得られますが、その結果は安定ではありません。

## 11.9.4 制約

ここまで読むと、計数ソートは非常に巧妙で、個数を数えるだけで効率的なソートを実現できると感じるかもしれません。しかし、計数ソートを利用するための前提条件は比較的厳格です。

計数ソートは非負整数にしか適用できません。ほかの型のデータに適用したい場合は、それらのデータを非負整数に変換でき、かつ変換の過程で要素間の相対的な大小関係が変わらないことを保証する必要があります。たとえば、負数を含む整数配列に対しては、すべての数値に定数を加えて正数へ変換し、ソート後に元へ戻すことができます。

計数ソートはデータ量が多く、値域が小さい場合に適しています。たとえば上記の例では \(m\) が大きすぎてはならず、そうでないと過剰な空間を消費します。また、\(n \ll m\) のとき、計数ソートは \(O(m)\) 時間を要するため、\(O(n \log n)\) のソートアルゴリズムより遅くなる可能性があります。

##### ご意見、ご質問、ご提案があればぜひコメントしてください