粛清しないO(n)のソート

bucket_sort.py

# 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]

inverse_mapping_sort.py

# 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]

radix_sort.py

# 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]))