基数ソート

Q: 基数ソートの時間計算量は?

基数ソートは `O(d·(n + k))` です。ここで `d` は桁数、`k` は基数です。固定幅の整数では実質的に `O(n)` となり、比較ソートより速い場合があります。追加空間は `O(n + k)` を使います。

最終更新 2026年7月1日

基数ソートは整数向けの非比較ソートです。値を比較する代わりに、数を桁ごとに並べ替えます。最下位桁 (LSD) 版はまず一の位を処理し、次に十の位、次に百の位を処理し、各桁で安定な計数ソートを用います。各パスが安定であるため、最上位桁を処理し終えた時点で配列全体がソートされます。上の再生ボタンを押して、各桁のパスが棒をどのように並べ替えるかを見てください。

基数ソートは O(d·(n + k)) 時間で動作します。ここで d は桁数、k は基数 (ここでは 10) です。固定幅の整数では実質的に線形で、O(n log n) の比較ソートを上回ることがあります。ただし桁やキーに分解できるデータにしか使えません。

時間計算量と空間計算量

ケース	計算量	備考
時間	O(d·(n + k))	d 桁、基数 k (d が固定なら線形)
空間	O(n + k)	出力配列 + 桁のカウント
安定	はい	各桁のパスは安定な計数ソート
比較を行う?	いいえ	値を比較せず桁で並べ替える
対象	整数/キー	一般的な比較可能オブジェクトには非対応

ステップごとの流れ

ステップ	何が起こるか
1	処理する桁数を知るために最大値を求める。
2	最下位桁 (一の位) から始める。
3	計数ソートを使ってその桁で配列を安定に並べ替える。
4	次のより上位の桁へ移る。
5	すべての桁位置を処理するまで繰り返す。

具体例

[170, 45, 75, 90, 2, 24, 66] をソート:

パス	配列	動作
開始	`[170, 45, 75, 90, 2, 24, 66]`	最大値は `170` なので、桁のパスが 3 回必要。
一の位	`[170, 90, 2, 24, 45, 75, 66]`	一の位で安定に並べ替え: `0, 0, 2, 4, 5, 5, 6`。
十の位	`[2, 24, 45, 66, 170, 75, 90]`	十の位で安定に並べ替え: `0, 2, 4, 6, 7, 7, 9` (`170` は `75` より前の順位を保つ)。
百の位	`[2, 24, 45, 66, 75, 90, 170]`	百の位で安定に並べ替え。`170` だけが `1` を持つため最後尾へ移動。ソート完了。

基数ソートを使うべき場面

使うべき場面	避けるべき場面
キーが桁に分解できる整数や固定長文字列である場合。	任意のオブジェクトをカスタム比較子で並べ替える必要がある場合。
キーの桁数 `d` が小さく有界で、`O(d·(n + k))` が `O(n log n)` を上回る場合。	キーが非常に長い、または有界でなく、`d` が大きくパスが高コストになる場合。
安定なソートが必要で、`O(n + k)` の追加空間を許容できる場合。	メモリが逼迫していて `O(n + k)` のバッファを許容できない場合。
値の範囲または基数 `k` が `n` に比べて控えめな場合。	`k` が巨大で、各計数ソートのパスが実行時間を支配する場合。

Radix Sortのコード

Python, JavaScript, Java, C++, Cによるクリーンで実行可能なRadix Sortの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。

PythonでのRadix SortのコードPython
1def radix_sort(a):2    # Sort by each decimal digit, least significant first3    max_value = max(a)4    exp = 15    while max_value // exp > 0:6        a = sort_by_digit(a, exp)7        exp *= 108    return a9
10
11def sort_by_digit(a, exp):12    buckets = [[] for _ in range(10)]13    for value in a:14        digit = (value // exp) % 1015        buckets[digit].append(value)16    # Concatenating buckets 0..9 keeps the sort stable17    return [value for bucket in buckets for value in bucket]18
19
20nums = [170, 45, 75, 90, 802, 24, 2, 66]21print("Before:", nums)22print("After: ", radix_sort(nums))
このコードをPythonプレイグラウンドで実行

JavaScriptでのRadix SortのコードJavaScript
1function radixSort(arr) {2    let a = [...arr];3    const max = Math.max(...a);4    // One counting pass per digit, least significant first5    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {6        const buckets = Array.from({ length: 10 }, () => []);7        for (const x of a) {8            buckets[Math.floor(x / exp) % 10].push(x);9        }10        a = buckets.flat();11    }12    return a;13}14
15const data = [170, 45, 75, 90, 802, 24, 2, 66];16console.log("Before:", data);17console.log("Sorted:", radixSort(data));
このコードをJavaScriptプレイグラウンドで実行

JavaでのRadix SortのコードJava
1import java.util.Arrays;2
3public class Main {4    static void radixSort(int[] arr) {5        int max = 0;6        for (int v : arr) max = Math.max(max, v);7        // One stable counting pass per decimal digit8        for (int exp = 1; max / exp > 0; exp *= 10) countingPass(arr, exp);9    }10
11    static void countingPass(int[] arr, int exp) {12        int n = arr.length;13        int[] out = new int[n];14        int[] count = new int[10];15        for (int v : arr) count[(v / exp) % 10]++;16        for (int i = 1; i < 10; i++) count[i] += count[i - 1];17        // Walk backwards to keep the pass stable18        for (int i = n - 1; i >= 0; i--) {19            int digit = (arr[i] / exp) % 10;20            out[--count[digit]] = arr[i];21        }22        System.arraycopy(out, 0, arr, 0, n);23    }24
25    public static void main(String[] args) {26        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};27        System.out.println("Before: " + Arrays.toString(arr));28        radixSort(arr);29        System.out.println("After:  " + Arrays.toString(arr));30    }31}
このコードをJavaプレイグラウンドで実行

C++でのRadix SortのコードC++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)11void countingPass(std::vector<int>& a, int exp) {12    std::vector<int> output(a.size());13    std::vector<int> count(10, 0);14    for (int x : a) ++count[(x / exp) % 10];15    for (int d = 1; d < 10; ++d) count[d] += count[d - 1];16    for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {17        int digit = (a[i] / exp) % 10;18        output[--count[digit]] = a[i];19    }20    a = output;21}22
23void radixSort(std::vector<int>& a) {24    int maxVal = *std::max_element(a.begin(), a.end());25    for (int exp = 1; maxVal / exp > 0; exp *= 10) {26        countingPass(a, exp);27    }28}29
30int main() {31    std::vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};32    std::cout << "Before: ";33    printVec(data);34    radixSort(data);35    std::cout << "After:  ";36    printVec(data);37    return 0;38}
このコードをC++プレイグラウンドで実行

CでのRadix SortのコードC
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5    for (int i = 0; i < n; i++) printf("%d ", a[i]);6    printf("\n");7}8
9// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)10void countingPass(int a[], int n, int exp) {11    int* output = malloc(n * sizeof(int));12    int count[10] = {0};13    for (int i = 0; i < n; i++) count[(a[i] / exp) % 10]++;14    for (int d = 1; d < 10; d++) count[d] += count[d - 1];15    for (int i = n - 1; i >= 0; i--) {16        int digit = (a[i] / exp) % 10;17        output[--count[digit]] = a[i];18    }19    for (int i = 0; i < n; i++) a[i] = output[i];20    free(output);21}22
23void radixSort(int a[], int n) {24    int maxVal = a[0];25    for (int i = 1; i < n; i++) {26        if (a[i] > maxVal) maxVal = a[i];27    }28    for (int exp = 1; maxVal / exp > 0; exp *= 10) {29        countingPass(a, n, exp);30    }31}32
33int main(void) {34    int data[] = {170, 45, 75, 90, 802, 24, 2, 66};35    int n = sizeof(data) / sizeof(data[0]);36    printf("Before: ");37    printArr(data, n);38    radixSort(data, n);39    printf("After:  ");40    printArr(data, n);41    return 0;42}
このコードをCプレイグラウンドで実行

基数ソートに関するよくある質問

基数ソートの時間計算量は?

基数ソートは O(d·(n + k)) です。ここで d は桁数、k は基数です。固定幅の整数では実質的に O(n) となり、比較ソートより速い場合があります。追加空間は O(n + k) を使います。

基数ソートは安定ですか?

はい。LSD 基数ソートは各桁で安定な計数ソートに依存しており、この安定性こそが桁ごとの手法で正しくソートされた結果を生み出します。

基数ソートはいつ使えますか?

基数ソートは、整数や固定長文字列のように桁や固定サイズのキーに分解できるデータに使えます。汎用の比較ソートではないため、カスタム比較子で任意のオブジェクトを並べ替えることはできません。

基数ソートと計数ソートはどう違いますか?

計数ソートは 1 つのキーで 1 パスで並べ替え、値の範囲と同じ大きさのカウント配列を必要とするため、値が広く散らばると性能が低下します。基数ソートは計数ソートを桁ごとに適用し、各パスのカウント配列を小さく (基数 k) 保つため、単純な計数ソートでは扱えない大きな値の範囲を処理できます。

なぜ LSD 基数ソートは最下位桁から始めるのですか?

最下位桁から始めることで、各安定パスがそれ以前のより下位の桁で確立された順序を保てます。最上位桁を処理する時点で、その桁が同じ要素は下位の桁によってすでに正しく並んでいるため、配列は最終的に完全にソートされます。最上位桁から先にソートするとこれが崩れ、別の再帰的手法 (MSD 基数ソート) が必要になります。

基数ソートは負の数を扱えますか?

直接は扱えません。基本的な桁の抽出は非負整数を前提としています。よくある対処は、最小値を加えてすべてを非負にオフセットする方法や、負の数と非負の数を別々にソートしてから連結する方法です。これを無視するのは、基数ソートを実データに適用する際によくあるバグです。