Pythonでのバケットソートを調べた際に出てきたソースコードなのですが、どういう動きでソートされているのかよくわからなかったので、自分なりに試行錯誤してコードの動きを調べてみた結果を備忘録として記載します。まだ初学者のため、基礎的な部分の説明にはなりますがご了承いただければと思います。
バケットソートとは
簡単にいうと、例えば1,2,3,と番号がついたバケツに①、②、③と書かれたボールをバケツの番号に合うように入れていき、順に出力する といったようなイメージのソート方法です。
アルゴリズムの中では比較的処理が早い部類になりますが、最大値分のバケツを用意しなくてはならないので、膨大なデータを処理するには向いておらず、少量のデータあるいは同じ数値が重複するような要素で効果を発揮します。
画像参照元：MoneyForward Engineer'sBlog
バケットソートのソースコード
今回参照した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)
コード解説
それぞれの条件ごとに、どういう結果になっているか解説していきます。
モジュール
import random
まずrandomモジュールを呼び出します。
関数
def counting_sort(A, max_num):
次に関数を定義します。
今回は変数にcounting_sort、引数にA, max_numを定義しています。
リスト
count_list = [0]*(max_num+1)
↓
count_list = [0]*(10+1) # 引数 max_num に仮に１０を設定をする
# count_list = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] となる
そして、リストを用意します。
このリストは、count_listとあるように、数値の個数をカウントするためのリストです。
なぜこのリストが必要なのかは後の条件でわかります。
[0]*(max_num+1)とすると、リストの中に０がmax_num + 1 個生成されます。
最大値＋１をする理由も後の条件でわかります。
for文①
for i in A:
count_list[i] += 1
# A = [random.randint(1,10) for _ in range(15)]の条件
# Aリストの中身は A = [8, 1, 9, 6, 10, 1, 7, 5, 4, 5, 2, 5, 1, 8, 5, 8]とする
ここからがややこしいです。
for文を使った条件文です。
まず、例で示している A のリストには、1〜10 までの整数値がランダムで 15 個生成されています。
そして、count_listのインデックス[ i ]にそれぞれの整数値を入れ、対応するインデックスの場所に 1 を加算します。
すると、count_listの中には、対応するインデックス値が何回出てきたのかが分かるリストになります。
イメージとして次のようなリストになります。
for i in A:
count_list[i] += 1
#リストの中身
A = [8, 1, 9, 6, 10, 1, 7, 5, 4, 5, 2, 5, 1, 8, 5, 8]
↓
count_list = [0 , 3 , 1 , 0 , 1 , 4 , 1 , 1 , 3 , 1 , 1]
"""（index = [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10])"""
例えば、A リストの中に 8 が 3 個あります。
そうなるとforループでは、count_list[8] += 1が3回行われます。
つまり、
1回目：count_list[8] = 1 (+=1)
2回目：count_list[8] = ２ (+=1)
3回目：count_list[8] = 3 (+=1)
となり、count_list[8]には3が入る と言うことになります。
ちなみに、インデックスは [ 0 ] からカウントされます。
Aリストは、1〜10の整数値を発生させているので、０ はありません。
つまり、前述した[0]*(max_num+1)の意味は、整数値の最大数 10 に 1 を足すことで
count_listのインデックス値と紐付けができるようになります。
for文②
i = 0
for num in range(len(count_list)): # count_listの長さを取得
for c in range(count_list[num]): # numには ０〜10 の整数値が入る
A[i] = num # i は初期値 = 0 で、Aリストの対応するインデックスにnumの整数値が代入される
i += 1 # i に代入された数値に 1 が加算される
またさらにややこしくなります。
for文のネストになります。
外側のfor文が実行されると、内側のfor文が実行されます。
外側のfor文
for num in range(len(count_list)):
まず、range(11)により 0〜10 までの整数値が生成され、11回ループすることになります。
変数numにはループするごとに、0 から順に代入されていきます。
例）
ループ 1 回目 ： num = 0
ループ 2 回目 ： num = 1
.
.
ループ 11 回目： num = 10
内側のfor文
for c in range(count_list[num]):
A[i] = num
i += 1
# A = [8, 1, 9, 6, 10, 1, 7, 5, 4, 5, 2, 5, 1, 8, 5, 8]
# count_list = [0 , 3 , 1 , 0 , 1 , 4 , 1 , 1 , 3 , 1 , 1]
次に内側ですが、rangeにはcount_listのインデックスが指定されています。
そしてそのインデックス値には、numを代入しています。
つまり、count_listのインデックスnumに対応する値がrangeに入ります。
実際にループが実行された場合を元に説明していきます。
ループ 1 回目
num = 0 なので、
range(count_list[num] = range(count_list[0] = range(0)
これは 0 回実行と言うことなので、処理は実行されず外側のループに戻ります。
ループ 2 回目
num = 1 なので、
range(count_list[num] = range(count_list[１] = range(3)
count_list[１]は、3 なので、3 回処理が実行されます。
内側の処理条件は以下になります。
A[i] = num # A リスト i のインデックスに対応する値に num を代入
i += 1 # i のインデックス値に 1 をプラス
# A = [8, 1, 9, 6, 10, 1, 7, 5, 4, 5, 2, 5, 1, 8, 5, 8]
初期値としてi = 0が設定されているので、A リストのインデックス 0 になります。
つまりA[0] = num となります。
num = 1ですので、A [0] = 1となり、A [0]の値 8 に 1 が代入されると言うことになります。
そして、i += 1は i に 1 を加算するので、A[1]となり1回目の処理が終了します。
2回目はA [1] = 1 となり、A [1]の値 1 に 1 が代入され、インデックス値に 1 が足されます。
3回目はA [2] = 1 となり、A [1]の値 9 に 1 が代入され、処理回数を満たしたので内側ループは終了します。
お気づきでしょうか？
つまりこういうことです。
- for文①で、
count_listで 1〜10 の整数値の出現回数をインデックス値に紐付けてカウント - for文②の外側のループで、
count_listの値の個数を 0 から順にnumに代入する - 内側のループで、
numの数値をcount_listのインデックス値と紐づけることにより、A リストにnumの数値がcount_listでカウントされた回数分代入される - 出現した数値のみが代入されていき、A リストには左から昇順に出現した数値がソートされていく。
といった仕組みとなっていたことがわかりました。
print(A)
counting_sort(A, 10)
print(A)
'''出力結果'''
A = [8, 1, 9, 6, 10, 1, 7, 5, 4, 5, 2, 5, 1, 8, 5, 8]
A = [1, 1, 1, 2, 4, 5, 5, 5, 5, 6, 7, 8, 8, 8, 9, 10]
まとめ
自分の学習した知識と理解で解説しておりますので、間違った箇所があるかもしれません。
もしお気づきの際はコメントいただけますと幸いです。