基数ソート

radix_sort.py

#!/usr/bin/env python3
# coding: utf-8
from typing import List, Tuple, Union


def radix_sort(values: List[int]) -> List[int]:
    """
    基数ソート
    :param values: 入力値
    :return: ソートされた値
    """
    sorted_values = values

    column = 0
    while column is not None:
        # 下位から(column + 1)桁目の値を基準にソート
        # ここでの計算量はO(n)
        sorted_values, column = inner_bucket_sort(sorted_values, column)

    return sorted_values


def inner_bucket_sort(values: List[int], column: int) -> Tuple[List[int], Union[int, None]]:
    """
    基数ソートの内部で使うバケットソート（鳩の巣ソート）
    :param values: 入力値
    :param column: ソート基準のカラム（最下位から 0 origin）
    :return: ソートされた値, 次のカラム（これ以上必要なければNone）
    """
    bits = 4
    radix = 1 << bits
    shifts = column * bits

    # 空のリストをradix個持つリストを作成
    # ここでの計算量はO(1)
    bucket: List[List[int]] = [[] for i in range(radix)]

    continues = False
    # バケツを作成（下位から(column + 1)桁目を比較）
    # ここでの計算量はO(n)
    for value in values:
        shifted = value >> shifts
        index = shifted % radix
        bucket[index].append(value)

        # radix以上の値があればまだ続く
        if shifted >= radix:
            continues = True

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

    if continues:
        column += 1
    else:
        column = None

    return sorted_values, column

test_radix_sort.py

# coding: utf-8
# python3 -m unittest
import unittest
import random

import radix_sort


class MyTestCase(unittest.TestCase):
    def test_radix_sort(self):
        # 100個の乱数を生成
        values = [random.randrange(0x100000000) for i in range(100)]

        # 基数ソートと組み込みのソートで比較
        output = radix_sort.radix_sort(values)
        expected = sorted(values)
        self.assertListEqual(output, expected)


if __name__ == '__main__':
    unittest.main()