バケットソート
読み：バケットソート
外語：bucket sort
ソートアルゴリズムの一つ。ビンソートとも呼ばれる。
概要
ソートしたい数列の最小値が1、最大値が100とする。このとき、数値を記憶する領域(バケット)を100個用意する。
数列の中に10という数値があるときは10番目のバケットに数値を放り込む。17という数値があるときは17番目のバケットに放り込む。すべての数値を放り込んだら、バケットから数値を取り出して整列させる。
特徴
数列の長さが20、最小値1、最大値10000というような場合、問題の大きさに対してバケットの数(作業領域)が大きくなりすぎる欠点がある。
その問題さえクリアできれば計算量はオー記法でO(n)であり、非常に高速にソートを行なうことができる。
その仕様上、整数値しかソートができない。
再検索