基数ソート単語

キスウソート

1.4千文字の記事
  • twitter
  • facebook
  • はてな
  • LINE

基数ソートはソートアルゴリズムの一種。

基本的に複合ソートとして使う。原理上バケットソートとの組み合わせが一般的、というかバケットソート一般化した仲のいい戚みたいな感じ。

元々は電子計算機発明以前に、パンチカードシステムカード処理用として19世紀から使われていた歴史の長いアルゴリズムである。実装によっては安定ソート

原理

基数ソートの対となるのは桁という概念を持てるデータである。数値であれば10進なり2進なりの数値の組み合わせとみなせるし、英文字列ならa-zの辞書順の並びと捉えられる。

こうしたデータを並び替える場合、最上位の桁を最優先とする順でソートオーダーが決定するので、桁ごとのソート結果を合算することで全体の並び替えができる。

考え方は大きく分けて二種類ある。

下からの基数ソート

  1. 最下位の桁をキーとしてデータソートする
  2. キーとなる桁を一つ上げて再度ソートする
  3. これを最上位の桁まで繰り返す

意味が最も強い最上位の桁を最後に並び替えるのがポイント。毎回全数の並び替えを生じるものの、ここが線形オーダーならば十分元は取れるというに考える。なお先に編成した下位の桁の順序を崩さないようにする必要があるため、補助には必ず安定ソートを使わなければならず、全体としても安定ソートになる。

一般に基数ソートといった場合こちらをすことが多いだろう。
通称はLSDLeast Significant Digit:最下位桁)である。

上からの基数ソート

  1. 最上位の桁でソートし、同じオーダーのものをグループ化する
  2. それぞれを再帰で並び替える
  3. これを各グループサイズが1になるまで繰り返す(108,216,342のようになっていたら、100の位の時点でそれぞれ1つしかないので下を見なくてよいということ)

下からの基数ソートとは異なり、こちらは値の数が減っていくところに特徴がある。実装はこちらの方が複雑だが、文字列のように長さが分からないものには上からの方が扱いやすい。

ちなみに上からの基数ソートを2進で構成した場合、よく見るとクイックソート分割基準値を、注する桁が0か1かに置き換えたものになっているので、別名バイナリクイックソートともいう。この時、値が0なら前詰め、1なら後ろ詰めにすることでソート済み部分を両端に寄せていき、インプレイスの基数ソートをするという面実装もある。上からの基数ソートは再帰構成なこともあって色々とバリエーションが多い。

通称はMSDMost Significant Digit:最上位桁)である。

性能検討

何と言っても桁が自然定義できるか、それによって値が効率よくさばけるか、である。ある程度データの性質、分布、規模などの条件がっていないとオーバーヘッドが大きいだけだが、使えるところでは線形オーダーが大きな威を発揮する。

それぞれのキーについての補助ソートはなんでもよいが、桁辺りの値の種類が事前に定まるのでバケットソート系を使うのが普通、というかそうできるのが持ち味。そのためよく使うのは数え上げソートとの組み合わせ。この時O(n)の補助ソート×桁数というオーダーになり非常に高速である。ただ、高速性を狙うと記憶スペースを食う傾向があり、インプレイスを狙うと実装が複雑というような面はある。

関連項目

この記事を編集する

掲示板

掲示板に書き込みがありません。

おすすめトレンド

急上昇ワード改

最終更新:2024/03/28(木) 22:00

ほめられた記事

最終更新:2024/03/28(木) 22:00

ウォッチリストに追加しました!

すでにウォッチリストに
入っています。

OK

追加に失敗しました。

OK

追加にはログインが必要です。

           

ほめた!

すでにほめています。

すでにほめています。

ほめるを取消しました。

OK

ほめるに失敗しました。

OK

ほめるの取消しに失敗しました。

OK

ほめるにはログインが必要です。

タグ編集にはログインが必要です。

タグ編集には利用規約の同意が必要です。

TOP