バケットソートについて調べてみた

はじめに

　大学の授業でバケットソートについて習ったので、自分自身の理解を深める目的で、最低限の情報だけ記事にまとめてみました。

操作

まず、初期値を0とした必要な長さのリストを用意し、ソート対象の配列の先頭から順に、対応したインデックスの値を増やします、その後、配列の先頭から、カウントされた数ずつ置き換えていくことで、ソートを行います。

可視化

計算量

　バケットソートの計算量はO(n)です。メモリは大量に使用しますが、比較をせずにソートを行うことができるので、非常に高速です。

安定ソートではない

　対応するインデックスの値を増やしていくことで、ソートを行うので、ソート前の状態は一切保持しません。したがって安定ソートではありません

内部ソートではない

　カウントするためのリストを用意しなければならないので、内部ソートではありません。何ならデータの範囲が大きいと、メモリを多く使用します。

コード

pythonで書くと、こんな感じです。

def bucket_sort(arr):
    n = len(arr)
    buckets = [0] * 20000

    for i in range(n):
        buckets[arr[i]] += 1

    index = 0
    for i in range(20000):
        if buckets[i]:
            for _ in range(buckets[i]):
                arr[index] = i
                index += 1

総評

強み

• 非常に高速

弱み

• 安定ソートでも内部ソートでもない
• データの範囲次第では、メモリを大量に使用する

→　データの範囲が分かっており、ソートする際の制約がない時に適性あり

最後に

　ここまで読んで下さりありがとうございました。個人で使う分には、メモリをそこまで気にする場面は多くないので、単純な数値のソートには、かなり有用な感じですね。個人で開発するときに、そこまで速度を求めることもあまりないですが。