基数ソートとは
- 各ビットを最下位ビットから順に操作するLSB(Least Significant Bit)、各ビットを上位から操作するMSB(Most Significant Bit)が存在する
- 比較を行わない非比較アルゴリズムで、データ全体を比較するのではなく、桁ごと、ビットごとに処理していく
- 同じ値を持つ要素の順序はソート前の状態を保つため、安全なソート
利点
- 安定した計算時間
- ビットごとに処理されるので、要素自体の大きさに左右されない
欠点
- 計算量はデータのビット数に依存するため、桁数が多い場合、計算量が増える
計算量
最良時間計算量：O(n * k)
最悪時間計算量：O(n * k)
平均時間計算量：O(n * k)
ソートアルゴリズム具体例
以下は、筆者が作成した基数ソートを用いた数字の並び替えプログラムです。
可視化デモ & 参考文献
