粛清しないソート

少し前、ソート業界ではスターリンソートというO(n)のソートではない何かが話題になっていたようです。

繰り返しますが、これはソートではない何かです。

というわけで、O(n)のちゃんとしたソートについて、アルゴリズムの概要と実装例をまとめてみました。

いろいろな制限（主に値の範囲）があるので汎用的なものではありませんが、定義域が特定の値に絞られているという状況はかなりあるので、場合によっては役立つものです。

逆写像ソート

値は一定の範囲の整数である必要があります。
もう少し正確には、その範囲を配列として保持できる必要があるのである程度狭くなければいけません。
「64bit整数でも一定の範囲の整数には違いないから問題ないだろ！」というわけにはいきません。

入力値である「n番目の値は何か？」を示す配列（写像）に対して、「この値は何番目か？」を示す逆写像を作成します。

逆写像のインデックスは値の昇順なので、そのままインデックスを取り出せば昇順にソートされた値が得られます。

以下のサンプルコードでは、簡単のため値は0から9までの重複のない整数値に限定していますが、少し工夫すれば値の上限・下限を変更できますし、値の重複にも対応できます。

# coding: utf-8
from typing import List


def inverse_mapping_sort(values: List[int]) -> List[int]:
    """
    逆写像ソート
    :param values: 入力値（0から9までの重複のない整数値とする）
    :return: ソートされた値
    """
    # 写像（インデックス→値）に対する逆写像（値→インデックス）
    inverse_map = [-1] * 10

    # 逆写像を作成
    # ここでの計算量はO(n)
    for index, value in enumerate(values):
        inverse_map[value] = index

    # inv_mapには値が小さい順にインデックスが入っているので、そのまま取り出せばOK
    # ここでの計算量はO(n)
    sorted_values = []
    for value, index in enumerate(inverse_map):
        if index >= 0:
            sorted_values.append(value)

    return sorted_values


print(inverse_mapping_sort([3, 1, 0, 8, 7, 9]))  # [0, 1, 3, 7, 8, 9]
print(inverse_mapping_sort([1, 2, 5, 4, 8, 6]))  # [1, 2, 4, 5, 6, 8]

バケットソート

これも値が一定の範囲しか取らない場合に使えるソートです。
概念はとても簡単で、「どの値がいくつ含まれているか」が入ったバケツを作成し、最後にバケツの先頭から値を取り出していきます。

以下の実装例は、分布数えソートに分類され、上記の逆写像ソートと似た実装です。値の重複にも対応しています。

人によっては「そもそもこれってソートと言えるの？」という印象を受けるかもしれません。

# coding: utf-8
from typing import List


def bucket_sort(values: List[int]) -> List[int]:
    """
    バケットソート
    :param values: 入力値（0から9までの整数値とする）
    :return: ソートされた値
    """
    # どの値がいくつ入っているかのバケツ
    bucket = [0] * 10

    # バケツを作成
    # ここでの計算量はO(n)
    for value in values:
        bucket[value] += 1

    # バケツの先頭から値を取り出す
    # ここでの計算量はO(n)
    sorted_values = []
    for value, count in enumerate(bucket):
        sorted_values += [value] * count

    return sorted_values


print(bucket_sort([3, 1, 0, 8, 7, 1, 9]))  # [0, 1, 1, 3, 7, 8, 9]
print(bucket_sort([1, 2, 5, 4, 8, 5, 6]))  # [1, 2, 4, 5, 5, 6, 8]

基数ソート

値はm桁の整数である必要があります。逆写像ソートやバケットソートのような極端な制約ではありません。
（正確には整数でなくてもm文字の文字列でもOKですが、簡単のために整数としておきます）

手作業で整数を並べ替えるときは最上位の桁から比較していくことが多いですが、基数ソートでは最下位の桁から比較していきます。
最初は1の位の値を基準に並べ替え、次の10の位の値を基準に並べ替え…と順に基準をずらしてゆき、最後に最上位桁の値を基準に並べ替えると全体がソートされます。

計算量はO(m * 1回あたりのソートにかかる計算量)ですが、10進数であれば内側のソートは値の種類が高々10種類なので高速なバケットソートが使え、O(m * n)で済みます。
値を整数に限定すれば、32bit整数でも高々m=10なので、全体としてO(n)とみなせます。

以下の実装例では、鳩の巣ソートに分類されるバケットソートを使っています。

# coding: utf-8
from typing import List


def radix_sort(values: List[int]) -> List[int]:
    """
    基数ソート
    :param values: 入力値（3桁の整数値とする）
    :return: ソートされた値
    """
    sorted_values = values[:]
    for m in range(3):
        # (10^m)桁目の値を基準にソート
        # ここでの計算量はO(n)
        sorted_values = inner_bucket_sort(sorted_values, m)

    return sorted_values


def inner_bucket_sort(values: List[int], m: int) -> List[int]:
    """
    基数ソートの内部で使うバケットソート（基数ソート用に少し変更）
    :param values: 入力値（3桁の整数値とする）
    :param m: 最下位からm桁目を基準にソート（0 origin）
    :return: ソートされた値
    """
    # [[]] * 10 だと参照の都合上うまくいかない
    # ここでの計算量はO(1)
    bucket = []  # type: List[List[int]]
    for i in range(10):
        bucket.append([])

    # バケツを作成（下からm桁目を比較）
    # ここでの計算量はO(n)
    k = 10 ** m
    for value in values:
        index = (value // k) % 10
        bucket[index].append(value)

    # バケツの先頭から値を取り出す
    # ここでの計算量はO(n)
    sorted_values = []
    for value in bucket:
        sorted_values += value

    return sorted_values


# [57, 104, 104, 123, 231, 234, 523, 803, 903, 980]
print(radix_sort([104, 903, 57, 231, 803, 104, 523, 980, 123, 234]))

おわかりいただけただろうか。

いずれも汎用的に使えるわけではありませんが、世の中にはちゃんとしたO(n)のソートも存在します。

粛清されたくない方はこちらをお使いください。