pythonでバケットソートの実装してみた

バケットソート(計数ソート)

pythonでは可変長の配列を作り出すことが簡単にできるのでバケットソートに関しては今まで学んだ知識を使わずに実装することができます．
今回扱うバケットソートには, 大きく分けて2種類の実装があります．
まずひとつは,可変個の要素を保持できるデータ構造を使ってバケツを表現する方法です．pythonのリストの考え方で言うと数値の種類分の二次元配列を用意し,その中にデータを入れていく方法です．
もうひとつは,いったん整列対象のデータを走査して値ごとの出現回数を数えておき,その出現回数に従った数値をリスト化する方法です．
この実装によるバケットソートのみを指して特に分布数えソート，計数ソート(Counting Sort)などと言うそうです．(参照)

バケットソートの実装

今回は後者の計数ソートの形をpythonで実装していきたいと思います．

import random
def counting_sort(A, max_num):
    #配列は0スタートのため
    count_list = [0]*(max_num+1)
    for i in A:
        count_list[i] += 1
    i = 0
    for num in range(len(count_list)):
        for c in range(count_list[num]):
            A[i] = num
            i += 1 
    
#要素数15の配列を作成
A = [random.randint(1,10) for _ in range(15)]
#randomに生成できる整数の最大値をmax_numとしてsortしていく
print(A)
counting_sort(A, 10)
print(A)

出力例

[9, 3, 8, 3, 6, 7, 6, 4, 8, 5, 9, 8, 2, 2, 2]
[2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 8, 9, 9]

pythonのリストを利用するとメモリを動的に増やすことができるのでバケットソートに関してはマージソート，クイックソートと比べると簡単に実装することができますね．
メモリの確保をしないといけないので要素数の数にだけ注意が必要になります．