#バケットソートとは？
各要素の数をカウントし、その要素を入れる配列番号を特定して、順に挿入していくソート方法。

用意する配列は２つ。

(1)カウンタ配列
各要素が何個あるかカウントする。

(2)ソート結果を入れる配列
ソートしたい配列と同じ要素数を持った配列を用意し、(1)で特定した要素を個数分だけ挿入していく。

**▼バケットソートのイメージ** [1,3,2,1,2,1]の配列の場合

1,2,3の入れ物（バケツ）を用意し、そこに各要素を入れて数をカウントする。（例：１は３つ、２は２つ、３は１つ）

その要素を順に並べていく。

参考：wikipedia

##バケットソートのメリデメ
###・メリット
直感的でわかりやすい。計算量ベースでは最速のソートアルゴリズム。

最大値が小さく、同じ数値が何度も重複する場合に効率的なソート。

###・デメリット
元の配列の最大値が大きい場合、その最大値分のバケツを用意しなければいけない。

下記条件の時には使えない。
・整数以外（小数点を含む）
　┗ バケットを用意できないため

・最大値が大きすぎる
　┗ カウンタ配列のメモリ使用量が膨大になってしまうため

**▼デメリットの例**（無駄なバケツが発生することを明示的に理解する）

list=[1,2,1,10]を並び替える場合
3~9は存在しないが、その分のバケツも用意しなければならない。

バケツ：	1	2	3	4	5	6	7	8	9	10
要素の数：	2	1	0	0	0	0	0	0	0	1

最大値が小さければソートは早いが、最大値が大きくなればなるほど用意するバケツの数も増える。

##バケットソートのコード実例

def bucket_sort(arr):
  arrc = [0]*(max(arr)+1)

  #カウンタ配列の作成。0始まり。0番目は常に０
  for i in arr:
    arrc[i] += 1

  #ソート結果を入れる配列を用意
  ans=[]

  for j in range(1, len(arrc)):
    ans.extend([j]*arrc[j])
  
  return ans

配列を足し合わせるextendを使う。
※appendは１つのまとまった要素として追加されるため、ここでは使えない。

確認

list=[8,3,1,2,3,3,10,7,6,7]
bucket_sort(list)

#[1, 2, 3, 3, 3, 6, 7, 7, 8, 10]

###extendを使わない方法

def bucket_sort2(arr):
  arrc = [0]*(max(arr)+1)

  #カウンタ配列の作成。0始まり。0番目は常に０
  for i in arr:
    arrc[i] += 1

  #ソート結果を入れる配列を用意
  ans=[]

  for j in range(1, len(arrc)):
    ans = ans+[j]*arrc[j]
  
  return ans

各バケットは同じ深さのため、単純に足していく。

確認

list=[8,3,1,2,3,3,10,7,6,7]
bucket_sort2(list)

#[1, 2, 3, 3, 3, 6, 7, 7, 8, 10]

###累積和から挿入位置を決めていく方法カウンタ配列を累積和に変換し、指定の要素を挿入する場所を見つけていく。

要素が重複している場合も考慮して、右から挿入したら、その要素が挿入される場所を-1する。

def bucket_sort3(arr):
  #配列内の最大値の数だけ要素数がある配列を作る。
  #累積和を求める時に、-1の要素を参照するため0からカウントする。
  arrc = [0] *(max(arr)+1)

  #配列の要素の数をカウント
  #指定の配列番号に１を足していく
  for i in arr:
    arrc[i] += 1

  #カウントを累積和に変換する。
  #現在の要素に一つ前の要素を足して、置き換えていく
  for j in range(1, len(arrc)) :
    arrc[j] = arrc[j] + arrc[j-1]
  
  #ソート結果を入れる配列を作る。配列の要素数は元の配列と同じ
  arrs = [0]*len(arr)
  
  #元の配列の要素を一つづつ取り出して、何番目に入るか調べて挿入していく
  for i in arr:

    #iを何番目に挿入するか調べる。ソート後の配列は0が不要のため、-1した場所に挿入する
    #同じ数が複数ある場合は一番右側から左に向かって埋めていく
    arrs[arrc[i]-1] =i
   
    #同じ要素が複数ある場合を考慮し累積和から、自分iの要素の数を一つ減らす
    arrc[i] -= 1

  return arrs

確認

list=[8,3,1,2,3,3,10,7,6,7]
bucket_sort3(list)

#[1, 2, 3, 3, 3, 6, 7, 7, 8, 10]

教材で累積和を使う方法が紹介されていたので処理を紐解いてみたが、正直、直感的にわかりにくい。