基本的に複合ソートの親として使う。原理上バケットソートとの組み合わせが一般的、というかバケットソートを一般化した仲のいい親戚みたいな感じ。
元々は電子計算機発明以前に、パンチカードシステムのカード処理用として19世紀から使われていた歴史の長いアルゴリズムである。実装によっては安定ソート。
基数ソートの対象となるのは桁という概念を持てるデータである。数値であれば10進なり2進なりの数値の組み合わせとみなせるし、英文字列ならa-zの辞書順の並びと捉えられる。
こうしたデータを並び替える場合、最上位の桁を最優先とする順でソートオーダーが決定するので、桁ごとのソート結果を合算することで全体の並び替えができる。
考え方は大きく分けて二種類ある。
意味が最も強い最上位の桁を最後に並び替えるのがポイント。毎回全数の並び替えを生じるものの、ここが線形オーダーならば十分元は取れるという風に考える。なお先に編成した下位の桁の順序を崩さないようにする必要があるため、補助には必ず安定ソートを使わなければならず、全体としても安定ソートになる。
一般に基数ソートといった場合こちらを指すことが多いだろう。
通称はLSD(Least Significant Digit:最下位桁)である。
下からの基数ソートとは異なり、こちらは値の数が減っていくところに特徴がある。実装はこちらの方が複雑だが、文字列のように長さが分からないものには上からの方が扱いやすい。
ちなみに上からの基数ソートを2進で構成した場合、よく見るとクイックソートの分割基準値を、注目する桁が0か1かに置き換えたものになっているので、別名バイナリクイックソートともいう。この時、値が0なら前詰め、1なら後ろ詰めにすることでソート済み部分を両端に寄せていき、インプレイスの基数ソートをするという面白い実装もある。上からの基数ソートは再帰構成なこともあって色々とバリエーションが多い。
通称はMSD(Most Significant Digit:最上位桁)である。
何と言っても桁が自然に定義できるか、それによって値が効率よくさばけるか、である。ある程度データの性質、分布、規模などの条件が揃っていないとオーバーヘッドが大きいだけだが、使えるところでは線形オーダーが大きな威力を発揮する。
それぞれのキーについての補助ソートはなんでもよいが、桁辺りの値の種類が事前に定まるのでバケットソート系を使うのが普通、というかそうできるのが持ち味。そのためよく使うのは数え上げソートとの組み合わせ。この時O(n)の補助ソート×桁数というオーダーになり非常に高速である。ただ、高速性を狙うと記憶スペースを食う傾向があり、インプレイスを狙うと実装が複雑というような面はある。
掲示板
掲示板に書き込みがありません。
急上昇ワード改
最終更新:2024/03/28(木) 22:00
最終更新:2024/03/28(木) 22:00
ウォッチリストに追加しました!
すでにウォッチリストに
入っています。
追加に失敗しました。
ほめた!
ほめるを取消しました。
ほめるに失敗しました。
ほめるの取消しに失敗しました。