基数ソート
1. 序章
このチュートリアルでは、ソートアルゴリズムである基数ソートについて説明します。
2. 線形時間での並べ替え
並べ替えの問題では、オブジェクトの配列と順序関係があります。 私たちの目標は、2つの連続する要素がそれぞれ正しい順序になるように並べ替えることです。
数値を扱う場合、関係はの1つです。 ここで、入力配列には整数が含まれていると想定し、減少せずに、つまり関係に従って並べ替える必要があります。 また、1ベースのインデックスを使用します。
比較ソートアルゴリズムは、要素を比較して相対的な順序を決定することにより、入力をソートします。 このようなメソッドは、たとえば、QuickSortおよびMergeSortです。 すべての比較ソートの最悪の場合の時間計算量の下限はです。
ただし、基数ソートアルゴリズムには、線形時間計算量があります。
3. 基数ソート
このアルゴリズムは、整数の配列を、最も小さいものから最も重要なものへと数字で並べ替えることによって並べ替えます。
まず、アルゴリズムは、カウントソートを使用して、それらを最下位桁でソートします。 その結果、0で終わる番号は、1で終わる番号よりも前になります。 次に、基数ソートは、このようにして取得した配列を2番目に小さい有効数字でソートし、前のステップの順序でタイを解除します。 したがって、各ステップで安定ソートアルゴリズムを使用する必要があります。
アルゴリズムは、最上位桁の数値をソートするまで、このように続行されます。 完了すると、入力配列全体が目的の順序になります。
3.1. 基数ソートの実行
例を見てみましょう：
まず、入力を最下位桁でソートします。 は元の配列の前にあり、番号は同じ桁で終わるため、最初のパスの後も同じ相対順序のままになります。 次に、配列を中央の桁で並べ替え、最後に最も重要な桁で並べ替えます。
3.2. 基数ソートの複雑さ
数字に数字（）があると仮定すると、基数ソートはループを繰り返します。 使用する安定ソートアルゴリズムに複雑さが含まれている場合、基数ソートの時間計算量はになります。
特に、 Counting Sort は、線形時間の非比較ソートアルゴリズムです。 これにより、基数ソートの複雑さは、になります。
3.3. 擬似コード
基数ソートの擬似コードは次のとおりです。
3.4. 証拠
の誘導により、基数ソートの正しさを証明できます。 ループ不変条件は、最下位桁を考慮して取得した数値がループ内のそれぞれに対してソートされることです。
不変量はループの前に自明に成り立つので、反復の開始時にtrueである場合、その終了時にもtrueであることを示しましょう。 したがって、それぞれの場合、-番目の反復が開始する前に、次のようになります。
ここで、-番目の最下位桁でソートします。 問題の桁が0であるすべての数値は、最下位桁が1である数値の前にあります。 結果として、
とが同じ数字で始まり、前者が後者（）の前にある場合、-番目のループの前になります。 これは、カウントソートの安定性に由来します。 -番目のループの前に不変量が保持されていると仮定しているので、次のことがわかります。 したがって、の場合、。
ループの終わりに、、だから、もし、それを証明したかったのです。
4. 基数ソートでの数字の定義
並べ替える構成要素を柔軟に定義できます。数字である必要はありません。 代わりに、連続する数字で構成されるグループの番号を並べ替えることができます。
たとえば、1桁の数字をそれぞれ2桁を含む5つの単語に分割できます。
一般に、整数にビットがある場合、ビットを一度にグループ化することにより、1桁の単語として書き込むことができます。 次に、カウントソートの複雑さはです。これを回と呼ぶので、基数ソートの複雑さはです。 最高のパフォーマンスを得るには、を最小化する値に設定する必要があります。
の場合、それ以降。 したがって、この場合、を設定すると、式が最小化されます。
それを仮定しましょう。 を選択すると、項はより速く増加するため、実行時間はです。 を設定すると複雑になります。 を使用すると、滞在中に分数が増加します。 つまり、。の場合に最適な選択です。
5. 基数ソートの最上位桁から最下位桁へ
数字の数字を最も重要なものから最も重要でないものへと並べ替えることができます。
最初のパスでは、最上位桁でソートします。 次に、同じ桁で始まる番号を含むサブ配列を再帰的に並べ替えます。 各呼び出しで、次の有効数字でソートします。 最後のものを並べ替えると、停止します。
擬似コードは次のとおりです。
ただし、問題は、カウントソートがインプレースアルゴリズムではないことです。 代わりに、新しい配列、つまり入力のソートされた順列を作成して返します。 そう、
が定数の場合、アルゴリズムのスペース複雑性は変更されませんが、実際にはメモリ消費に影響します。 そのため、再帰基数ソートはメモリ制限が厳しいアプリケーションには適していません。
6. 非整数の並べ替え
このアルゴリズムを非整数に適用できますか？ 一般に、数字は数字である必要はありません。
整数マッピングを設計しても基数ソートが適用できない場合があります。たとえば、入力オブジェクトに、それぞれが数百万の可能な値を持つフィールドを持たせます（）。 ただし、桁数が多すぎます。 その結果、カウントソートのパフォーマンスが低下し、必要以上のメモリが消費されます。
ハッシュマップを使用してメモリ消費を削減することもできますが、高品質のhash関数を設計する必要があります。 ただし、ハッシュ値は時間の経過とともに変化するため、ハッシュルックアップの最悪の場合の複雑さはになります。 したがって、このアプローチは実際にはまだ非効率的です。
7. 結論
この記事では、基数ソートを紹介しました。 これは安定した線形時間ソートアルゴリズムです。 基数ソートには線形の時間計算量がありますが、その下に隠れている乗法係数は、実際には漸近的に悪い比較ソートよりも効率が低くなります。 また、カウントソートはインプレースアルゴリズムではないため、基数ソートはクイックソートなどのアルゴリズムよりも多くのメモリを消費する可能性があります。
