基数ソート

基数ソート（ラディックスソート）

基数ソートは、比較によらないソートアルゴリズムの一つで、位取り記数法で表現できるデータに対して有効な手法です。このアルゴリズムは、データの最下位桁から順にソートを行い、最終的に最上位桁でソートすることで、データ全体を順序通りに並べ替えます。

アルゴリズムの概要

基数ソートは、複数のキー（桁）を持つデータに対して、優先順位の高いキーから順にソートを行うという考えに基づいています。例えば、3桁の数字であれば、1の位、10の位、100の位というように、下位の桁から上位の桁へと順番にソートを進めます。

具体的な手順は以下の通りです。

1. キーの分類: 入力データを、各桁（キー）の値に基づいて分類します。
2. 下位桁からのソート: 最も下位の桁からソートを開始します。この際、値の範囲が限定されているため、バケットソートなどの効率的なソートアルゴリズムが用いられます。ここで、安定なソートアルゴリズムを使用する必要があります。
3. 桁上げ: 次に上位の桁に対してソートを行います。これを最上位桁まで繰り返します。

たとえば、以下のような数列を考えてみましょう。

`170, 45, 75, 90, 2, 24, 802, 66`

1. 1の位でソート:
`170, 90, 2, 802, 24, 45, 75, 66`
2. 10の位でソート:
`2, 802, 24, 45, 66, 170, 75, 90`
3. 100の位でソート:
`2, 24, 45, 66, 75, 90, 170, 802`

このようにして、数列全体がソートされます。

計算量と安定性

基数ソートの計算量は、データの数をn、桁数をkとすると、O(nk)となります。また、適切な実装を行うことで、安定ソートを実現できます。安定ソートとは、同じ値を持つ要素の順序が、ソート後も変化しない性質のことです。

前提条件

基数ソートを適用するためには、以下の前提条件を満たす必要があります。

データの種類: ソート対象のデータの種類が有限であること。
最大値と最小値: データにおける最大値と最小値が明確であること。
データ形式: 全ての入力データが、例えば「3桁の整数」や「2文字のアルファベット」のように、決まった形式であることが分かっていること。

応用例

基数ソートは、以下のような場面で応用されています。

コンピュータ内部でのデータソート: コンピュータ内部では、全てのデータがバイナリ形式で表現されているため、2進数や2のn乗進数での基数ソートが可能です。
浮動小数点数のソート: IEEE 754形式の浮動小数点数のソートに用いられることがあります。この形式では、ビット表現を整数として扱うことで、効率的なソートが可能です。
パンチカードのソート: 歴史的には、パンチカードのソートに基数ソートの概念が用いられていました。カードの穴の位置に応じて、カードを振り分けることで、ソートを実現します。

注意点

負の値を含む整数のソートでは、符号付き数値表現に応じて、若干の注意が必要です。
浮動小数点数のソートでは、表現形式に依存した処理が必要となる場合があります。

まとめ

基数ソートは、データの形式が既知である場合に非常に効率的なソートアルゴリズムです。特に、整数や文字列など、桁や文字をキーとしてソートできる場合に効果を発揮します。安定ソートとしての実装も容易であり、幅広い応用が可能です。

もう一度検索