Last active
September 17, 2019 14:33
-
-
Save shimataro/34e7b933a7d125c0308ee584ff47e539 to your computer and use it in GitHub Desktop.
基数ソート
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # 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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment