バケットソート（ビンソート）

概要

あらかじめデータがとりうる値を入れる容器（バケット）を用意しておき、値を対応する容器に移すことでソートを行うアルゴリズムです。

データがとりうる値がわかっていなければソートのための容器を準備することができないので、このアルゴリズムは使えません。

使用例

1.数字を昇順に並べる

0~9の範囲で数字がいくつか与えられるので、それを昇順に並べるアルゴリズムを書いてみます。

コード

def bucket(num_list):
    bucket = [0] * 11
    ans = []

    for i in num_list:
        bucket[i] += 1

    for i in range(1, 11):
        ans.extend([i] * bucket[i])
    
    return ans

num_list = [1, 9, 8, 1, 3, 2, 8, 6, 1, 6]
print(bucket(num_list))
# [1, 1, 1, 2, 3, 6, 6, 8, 8, 9]

解説

0~9の数字を入れるためのリスト（bucket）を用意する
bucketに値を入れていく
bucketの中身を順に出力する

まず、0~9の数字を入れることのできるリストを準備します。

与えられた数字のリスト（num_list）でfor文を回し、どの数字が何回登場しているかを数えます。

数え終わったら、登場した数字をその回数分出力すれば終了です。

2.Ringo's Favorite Numbers 2（ABC200_C）

N個の正整数からなる数列Aが与えられた時、1 <= i < j <= Nかつ$A_i$-$A_j$が200の倍数である(i, j)の組の個数を求めなさい。

入力形式

N
A1 A2 ... AN

入力例

6
123 223 123 523 200 2000

コード

# 入力の読み込み
n = int(input())
a = list(map(int, input().split()))
# バケットを用意
bucket = [0] * 200
ans = 0

# バケットに数値を入力
for i in a:
    bucket[i % 200] += 1

# 解答を計算
for i in bucket:
    ans += i * (i - 1) // 2

print(ans)

解説

0~199（200で割った余り）の数字を入れるためのリスト（bucket）を用意する
与えられた数字のリストをfor文で回し、200で割った余りをリストに入力していく
求めたい場合の組の個数を計算する

前提として、「$A_i$-$A_j$が200の倍数である」というのは**「$A_i$を200で割った余りと$A_j$を200で割った余りが一致する」ということと同値になります。
したがって、求めたい数値は「$A_i$を200で割った余りと$A_j$を200で割った余りが一致する組の個数」**と言い換えることができます。

それではコードの説明をしていきます。

まず、問題1と同じように、数字を入れるためのリスト（bucket）を用意しておきます。
今回は、**「正の整数を200で割った余り」**を入れるためのリストなので、0~199の数字を入れるリストになります。

与えられた正の整数のリスト（a）をfor文で回し、200で割った余りをbucketに追加していきます。

n個の要素から2個の要素を選び取る場合の数はn(n-1)/200なので、bucketをもとに答えを得ることができます。

他のアルゴリズムに関する記事

筆者より

アルゴリズム初心者なので、間違っている点や説明不足な点は教えていただけるとありがたいです！

参考にさせていただいたサイト