-
@Lambda
- 2017.10.9
- PV 56
バケットソート
ー 概要 ー
とりうる値の範囲がわかっているときに要素比較なしにソートできるアルゴリズム.
仮想的なバケツに値を追加していき全ての確認が終わったら値を小さいバケツから取り出していく.
この章を学ぶ前に必要な知識
条件
- データの値の取りうる範囲がわかっていること
- メモリを多く使用しても問題ないこと
ポイント
- 平均計算時間はO(n + k) : kはバケツの数
解 説
複数の仮想的なバケツがあるとして、そこのバケツにソートするデータの値を入れていく。
全て入れ終えたら今度は、小さいバケツから取り出していく。
平均計算時間はO(n)O(n)となってかなり早いが、メモリを多く使用する可能性がある。 | バケットソート概要 |
 | 10の桁ごとに用意されたバケツに入力データを入れていく.
0の箱には10の位が0の5を,
1の箱には10の位が1の12をといった具合。
バケツには複数の値を入れてよいですが、
取り出すときにはバケツの中でソートが必要です。 |
この章を学んで新たに学べる
Comments