基数ソート
コンピュータの内部では、どんなデータもバイナリであるから、それをそのまま利用して2進ないし2進の基数ソートができる。
負の値を含む一般の整数の表現の場合(符号付数値表現を参照)、それぞれの表現毎の性質に応じて多少の注意が必要だが、基本的な所は同様におこなうことができる。
浮動小数点形式では、
近年ではほぼ全てである標準規格のIEEE 754形式では、float a, b が与えられたとき、a>b>0なら*(int*)&a>*(int*)&bとなるため、指数部と仮数部に分ける必要も、整数に近似する必要もない。 http://codercorner.com/RadixSortRevisited.htm を参照
任意の浮動小数点形式の場合は、
適当なファクターを乗じて整数に近似して基数ソートを適用した後、元の値をバブルソート等で並び替える
内部表現を指数部・仮数部に分け、指数部を仮数部の上位キーとして基数ソートを行う(数値の内部表現の形式に依存する)
などの方策がある。
コンピュータ以外での応用に、周辺部に穴の開いた紙カードの、穴から外側の部分の紙を情報に応じて切り欠いたもの(パンチカード#ハンドソートパンチカード)のソート方法というものがある。歴史的な順序としてはこれのほうが(従って基数ソートというアイディアそのものも)、電子式のコンピュータが誕生するより古くからある。穴の場所に串を通し持ち上げると、その穴のところを切り欠いたカードが残り、切り欠いてないカードが選び出される。そうして選び出したカードを片側に寄せる。二進法の下の桁からこの操作を繰り返すと、基数ソートになる。
基数ソートは、「複数のキーについて優先順位のあるソート」と考えることができる。すなわち、最上位桁が最も優先順位の高いキー、次いでその下の桁が2番目の優先順位のキー、3番目の桁が......、といった要領である。以下、そのような考えで「キー」という用語を使って説明する。
入力の数列は、いくつかのキーに分類する。例えば、3桁の数字であれば、1の位・10の位・100の位に分けて分類する。
それぞれのキーについて、下位のキーからソートする。この際、値の範囲が有限であることからバケットソートが効率的である。(ここで、O(n)でないソートアルゴリズムを用いると、全体の計算時間が O(nk)でなくなることに注意。また、安定なソートでなければならない。)
たとえば、
という数列を1の位についてソートすると、
となる。さらに、10の位についてソートすると、
となる。最後に、100の位についてソートすると、
となり、ソートが完了する。