Javaでの基数ソート - 開発者ドキュメント

1. 序章

このチュートリアルでは、 Radix Sort について学習し、そのパフォーマンスを分析して、その実装を確認します。

ここでは基数ソートを使用して整数をソートすることに焦点を当てていますが、これは数値だけに限定されません。 文字列、などの他のタイプのソートにも使用できます。

簡単にするために、数値が基数（基数）10で表される10進法に焦点を当てます。

2. アルゴリズムの概要

基数ソートは、桁の位置に基づいて数値をソートするソートアルゴリズムです。基本的には、数値の桁の桁の値を使用します。 マージソート、挿入ソート、バブルソートなど、他のほとんどのソートアルゴリズムとは異なり、数値を比較しません。

基数ソートは、安定ソートアルゴリズムをサブルーチンとして使用して数字をソートします。ここでは、基数を使用してすべての位置の数字を並べ替えるサブルーチンとして、並べ替えのカウントのバリエーションを使用しました。 Counting sort は安定したソートアルゴリズムであり、実際にはうまく機能します。

基数ソートは、最下位桁（LSD）から最上位桁（MSD）に数字を並べ替えることによって機能します。 MSDからの数字を処理するために基数ソートを実装することもできます。

3. 簡単な例

例を使ってどのように機能するかを見てみましょう。次の配列を考えてみましょう。

3.1. 反復1

LSDからの数字を処理し、MSDに向かって移動することにより、この配列を並べ替えます。

それでは、1桁の数字から始めましょう。

最初の反復後、配列は次のようになります。

番号は1桁の数字に従ってソートされていることに注意してください。

3.2. 反復2

10の位の数字に移りましょう：

これで、配列は次のようになります。

数字の7は、10の位に数字がないため、配列の最初の位置を占めていることがわかります。これは、10の位に0があると考えることもできます。

3.3. 反復3

百の位の数字に移りましょう：

この反復の後、配列は次のようになります。

そして、アルゴリズムはここで停止し、すべての要素がソートされます。

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); 

}

サブルーチンでは、基数（range）を使用して、各桁の出現回数をカウントし、その頻度をインクリメントしました。したがって、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); 
}