Javaの基数ソート

1. 前書き

このチュートリアルでは、Radix Sortについて学び、そのパフォーマンスを分析し、その実装を見ていきます。
*ここでは、整数をソートするためにRadix Sortを使用することに焦点を当てていますが、数字だけに限定されません。* _String、_などの他のタイプをソートするためにも使用できます。
シンプルに保つために、数値が基数(基数)10で表現される10進法に焦点を当てます。

2. アルゴリズムの概要

基数ソートは、数字の位置に基づいて番号をソートするソートアルゴリズムです。 基本的に、数値の桁の場所の値を使用します。 * link:/java-merge-sort[Merge Sort]、https://www.baeldung.com/java-insertion-sort [Insertion Sort]など、他のほとんどのソートアルゴリズムとは異なります。 、https://www.baeldung.com/java-bubble-sort [Bubble Sort]、数値を比較しません。*
基数ソートは、数字をソートするサブルーチンとしてlink:/stable-sorting-algorithms [安定したソートアルゴリズム]を使用します。 ここでは、基数を使用してすべての位置の数字を並べ替えるサブルーチンとして、並べ替えの並べ替えを使用しました。 link:/java-counting-sort[Counting sort]は安定したソートアルゴリズムであり、実際にうまく機能します。
基数ソートは、最下位桁(LSD)から最上位桁(MSD)に数字をソートすることにより機能します。 また、Radixソートを実装して、MSDからの数字を処理することもできます。

3. 簡単な例

例でどのように機能するかを見てみましょう。 次の配列を考えてみましょう。
link:/uploads/Array-100x10.png%20100w []

繰り返し1:

LSDからの数字を処理し、MSDに向かって移動することにより、この配列をソートします。
1桁の数字から始めましょう。
link:/uploads/Before-Iteration-1-100x10.png%20100w []
最初の反復の後、配列は次のようになります。
link:/uploads/After-Iteration-1-100x10.png%20100w []
数字は1桁の数字に従ってソートされていることに注意してください。

繰り返し2:

十の位の数字に移りましょう:
link:/uploads/Before-Iteration-2-100x10.png%20100w []
配列は次のようになります。
link:/uploads/After-Iteration-2-100x10.png%20100w []
10の位に数字がないため、番号7が配列の最初の位置を占めていることがわかります。 これは、10の位に0があると考えることもできます。

イテレーション3:

数百の位置の数字に移りましょう:
link:/uploads/Before-Iteration-3-100x10.png%20100w []
この反復の後、配列は次のようになります。
link:/uploads/After-Iteration-3-100x10.png%20100w []
そして、アルゴリズムはここで停止し、すべての要素がソートされます。

4. 実装

実装を見てみましょう。
void sort(int[] numbers) {
    int maximumNumber = findMaximumNumberIn(numbers);
    int numberOfDigits = calculateNumberOfDigitsIn(maximumNumber);
    int placeValue = 1;
    while (numberOfDigits-- > 0) {
        applyCountingSortOn(numbers, placeValue);
        placeValue *= 10;
    }
}
このアルゴリズムは、配列内の最大数を見つけて、その長さを計算することにより機能します。 このステップは、すべての場所の値に対してサブルーチンを確実に実行するのに役立ちます。
たとえば、配列_ [7、37、68、123、134、221、387、468、769] _では、最大数は769で、長さは3です。
したがって、すべての位置の数字に対してサブルーチンを3回繰り返し適用します。
void applyCountingSortOn(int[] numbers, int placeValue) {

    int range = 10 // decimal system, numbers from 0-9

    // ...

    // calculate the frequency of digits
    for (int i = 0; i < length; i++) {
        int digit = (numbers[i] / placeValue) % range;
        frequency[digit]++;
    }

    for (int i = 1; i < range; i++) {
        frequency[i] += frequency[i - 1];
    }

    for (int i = length - 1; i >= 0; i--) {
        int digit = (numbers[i] / placeValue) % range;
        sortedValues[frequency[digit] - 1] = numbers[i];
        frequency[digit]--;
    }

    System.arraycopy(result, 0, numbers, 0, length);

}
サブルーチンでは、基数_(範囲)_を使用して、各桁の出現をカウントし、その頻度をインクリメントしました。 したがって、0〜9の範囲の各ビンには、桁の頻度に基づいた値があります。 次に、周波数を使用して、配列内の各要素を配置します。 これにより、配列の並べ替えに必要なスペースを最小限に抑えることができます。
次に、メソッドをテストしましょう。
@Test
public void givenUnsortedArray_whenRadixSort_thenArraySorted() {
    int[] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7};
    RadixSort.sort(numbers);
    int[] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769};
    assertArrayEquals(numbersSorted, numbers);
}

5. 基数ソートとカウントソート

サブルーチンでは、_frequency_配列の長さは10(0-9)です。 Counting Sortの場合、_range_は使用しません。 _frequency_配列の長さは、配列1の最大数になります。 したがって、Radix Sortはビンを使用してソートしますが、それらをビンに分割しません。
ソートのカウントは、配列の長さが配列の最大値よりも小さくない場合に非常に効率的ですが、Radixソートでは配列の値を大きくすることができます。

6. 複雑

基数ソートのパフォーマンスは、数字のソートに選択された安定したソートアルゴリズムに依存します。
ここでは、基数_b_の_n_数値の配列をソートするためにRadixソートを使用しました。 この例では、ベースは10です。 Counting Sortを_d_回適用しました。ここで、_d_は桁数を表します。 したがって、Radix Sortの時間の複雑さは_O(d *(n + b))_になります。
ここではサブルーチンとしてCounting Sortのバリエーションを使用しているため、スペースの複雑さは_O(n b)_です。

7. 結論

この記事では、Radixソートアルゴリズムについて説明し、その実装方法を説明しました。
いつものように、コードの実装はhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[Github上]で入手できます。