このチュートリアルでは、Pythonのバケットソートの理論と実装を学びます。
バケットソートは比較型のアルゴリズムで、ソートしたいリストの要素をバケット(Bucket)またはビン(Bins)に割り当てます。これらのバケットの内容は、通常、別のアルゴリズムでソートされます。ソート後、バケットの内容が追加され、ソートされたコレクションが形成される。
バケットソートは、リストを並べ替えるための散布順アプローチと考えることができます。これは、要素がまずバケットに散布され、その中で並べられ、最後に新しい並べ替えられたリストに集められるという事実からきています。
Pythonでバケットソートを実装し、その時間複雑性を分析する。
バケットソートの仕組み
その具体的な実装に入る前に、アルゴリズムの手順を説明しましょう。
- 空のバケツのリストをセットする。バケツは配列の各要素に対して初期化されます。
-
- バケットリストを繰り返し処理し、配列から要素を挿入する。各要素がどこに挿入されるかは、入力リストとその中で最大の要素に依存する。各バケツには0…n`個の要素を入れることができる。これについては、アルゴリズムのビジュアルプレゼンテーションで詳しく説明します。
-
- 空でないバケツをソートする。これは、どんなソートアルゴリズムでも可能です。今回は小さなデータセットを扱うので、各バケツの要素はそれほど多くはないだろうから、ここでは挿入ソートがうまく機能する。
-
- バケツを順番に見ていく。各バケツの内容がソートされたら、それらを連結すると、基準に基づいて要素が並べられたリストができあがります。
それでは、このアルゴリズムがどのように動作するのか、視覚的に表現してみましょう。例えば、これが入力リストであるとする。
最大の要素は1.2で、リストの長さは6である。この2つを使って、各バケットの最適な「大きさ」を求めます。この数値は、最大の要素をリストの長さで割ることで得られます。この場合、「1.2/6」なので、「0.2」です。
この size で要素の値を割ると、各要素のバケツに対応するインデックスが得られます。
ここで、空のバケットを作成します。リストの要素と同じ数のバケツを用意することになります。
各要素をそれぞれのバケツに入れます。最初の要素である 1.2/0.2 = 6 を考慮すると、それぞれのバケツのインデックスは 6 となります。この結果がリストの長さ以上であれば、1を引くだけでうまくリストに収まるでしょう。これは一番大きな数字に対してのみ起こることです。なぜなら、一番大きな要素を長さで割ることによって size を得たからです。
この要素を、インデックスが 5 のバケツに入れることにします。
同様に、次の要素には 0.22/0.2 = 1.1 というインデックスを付けます。これは10進数なので、床を付けます。これを四捨五入して1とし、その要素を2番目のバケツに入れます。
この処理を、最後の要素がそれぞれのバケツに入るまで繰り返します。バケツの中身は次のような感じです。
さて、空でないバケツの中身を並べ替えてみましょう。挿入ソートは、このような小さなリストでは無敵なので、これを使用します。挿入ソート後のバケツはこのようになります。
あとは、空でないバケットを巡回して、要素を連結してリストにするだけです。これでソートされ、準備が整いました。
Pythonによるバケットソートの実装
それでは、Pythonでこのアルゴリズムを実装してみましょう。まずは bucket_sort() 関数自身から。
def bucket_sort(input_list):
# Find maximum value in the list and use length of the list to determine which value in the list goes into which bucket
max_value = max(input_list)
size = max_value/len(input_list)
# Create n empty buckets where n is equal to the length of the input list
buckets_list= []
for x in range(len(input_list)):
buckets_list.append([])
# Put list elements into different buckets based on the size
for i in range(len(input_list)):
j = int (input_list[i] / size)
if j != len (input_list):
buckets_list[j].append(input_list[i])
else:
buckets_list[len(input_list) - 1].append(input_list[i])
# Sort elements within the buckets using Insertion Sort
for z in range(len(input_list)):
insertion_sort(buckets_list[z])
# Concatenate buckets with sorted elements into a single list
final_output = []
for x in range(len (input_list)):
final_output = final_output + buckets_list[x]
return final_output
この実装は非常に簡単です。まず、パラメータ size を計算します。そして、空のバケツのリストをインスタンス化し、その値と各バケツの size に基づいて要素を挿入しています。
挿入された後、各バケットに対して insertion_sort() を呼び出します。
def insertion_sort(bucket):
for i in range (1, len (bucket)):
var = bucket[i]
j = i - 1
while (j >= 0 and var < bucket[j]):
bucket[j + 1] = bucket[j]
j = j - 1
bucket[j + 1] = var
そして、この状態で、リストを投入し、バケットソートを実行してみましょう。
def main():
input_list = [1.20, 0.22, 0.43, 0.36,0.39,0.27]
print('ORIGINAL LIST:')
print(input_list)
sorted_list = bucket_sort(input_list)
print('SORTED LIST:')
print(sorted_list)
このコードを実行すると、次のような結果が返ってきます。
Original list: [1.2, 0.22, 0.43, 0.36, 0.39, 0.27]
Sorted list: [0.22, 0.27, 0.36, 0.39, 0.43, 1.2]
バケットソートタイムコンプリシティ
最悪の場合の複雑さ
もし私たちが扱っているコレクションが短い範囲にある場合（この例ではそうでした） – 多くの要素が1つのバケツに入り、多くのバケツは空になるのが一般的です。
すべての要素が同じバケツに入る場合、複雑さはバケツの中身をソートするためのアルゴリズムにのみ依存します。
私たちは挿入ソートを使用しているので、その最悪の場合の複雑さは、リストが逆順のときに輝きを増します。したがって、バケットソートの最悪複雑度もO(n2)となります。
ベストケースの複雑さ
最良のケースは、すべての要素がすでにソートされていることである。さらに、要素は一様に分布している。これは、各バケットが同じ数の要素を持っていることを意味します。
とはいえ、バケットの作成には O(n) がかかり、挿入ソートには O(k) がかかるので、複雑さは O(n+k) となります。
平均的な場合の複雑さ
平均値の場合は，現実のコレクションの大部分で発生する．ソートしたいコレクションがランダムである場合。この場合、バケットソートはO(n)で終了し、非常に効率的である。
結論
まとめとして、バケットソートとは何かという導入から始まり、Pythonでの実装に入る前に知っておくべきことを議論してきました。実装の後、簡単な複雑さの解析を行いました。