この章を学ぶ前に必要な知識
条件
- データの表記種類が0 ~ 9のように決まっていて大小も決まっている
- アルファベットなども同様に使用可能
ポイント
- 最悪計算時間は n * k /sとなる安定ソート
- 計算機においてはfloat等でも変換なしで同様に扱える
解 説
アルゴリズムのやり方はとても簡単となっていて、O(nk)O(nk)の計算時間でソートができる比較によらない安定なソート手法。
(kは0~9やa~zの種類の数, nはデータ数)
nが多くkが少ないときに高速になる.
| 基数ソート |
 | k = 3で n = 7の場合の基数ソート
1の位からソートを行っていき、
100の位のソートを終えると全体のソートが完了している。 |
この章を学んで新たに学べる
Comments
