バケットソートの改良版。基数に注目して、桁の小さいほうからバケットソートを行なう。これによりバケットの数が10で済む。

計算量は最大桁数をmとしたとき、O(mn)である。

基数ソートの途中経過
829 601 150 207 533 187 659 391 232 793  初期状態
150 601 391 232 533 793 207 187 829 659  1の位の処理
601 307 829 232 533 150 659 187 391 793  10の位の処理
150 167 232 307 391 533 601 659 793 829  100の位の処理(終わり)

リンク

関連する用語
ソート
バケットソート
外部ソート
基数

[再検索] [戻る]