Skip to content

Instantly share code, notes, and snippets.

@shimataro

shimataro/bucket_sort.py

Created September 15, 2019 17:17
Show Gist options
  • Save shimataro/75a549ae332d0f70df1f47581cf6da35 to your computer and use it in GitHub Desktop.
Save shimataro/75a549ae332d0f70df1f47581cf6da35 to your computer and use it in GitHub Desktop.
Download ZIP
粛清しないO(n)のソート
Raw
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]
Raw
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]
Raw
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]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment