Javaでのソートのカウント

投稿日: 2019-10-18 2022-11-04
タグ: Algorithms, Java

1. 概要

マージソートのような汎用ソートアルゴリズムは入力について何も想定していないため、最悪の場合、 O（n log n）を打ち負かすことはできません。逆に、カウントソートには、線形時間ソートアルゴリズムとなる入力に関する仮定があります。

このチュートリアルでは、カウントソートの仕組みを理解し、それをJavaに実装します。

2. カウントソート

ほとんどの従来の並べ替えアルゴリズムとは対照的に、並べ替えをカウントしても、要素を比較して特定の入力を並べ替えることはありません。代わりに、入力要素が[0、k]の範囲のn個の整数であると想定します。 k = O（n）、の場合、カウントソートは O（n）時間で実行されます。

したがって、カウントソートを汎用のソートアルゴリズムとして使用することはできないことに注意してください。ただし、入力がこの仮定に沿っている場合は、かなり高速です。

2.1. 周波数配列

入力配列を[0、5]の範囲の値でソートするとします。

初め、入力配列内の各数値の出現をカウントする必要があります。配列Cでカウントを表す場合、C[i]は入力配列の数値iの頻度を表します：

たとえば、5は入力配列に3回出現するため、インデックス5の値は3に等しくなります。

配列Cが与えられたら、各入力要素以下の要素の数を決定する必要があります。例えば：

1つの要素がゼロ以下である、つまり、 C[0]に等しいゼロ値が1つだけあります。
2つの要素は1以下であり、 C [0] + C[1]に等しい
4つの値は2以下であり、 C [0] + C [1] + C[2]に等しい

したがって、Cでn個の連続する要素の合計を計算し続けると、入力配列の数n-1以下の要素の数を知ることができます。とにかく、この簡単な式を適用することで、 C 次のように：

2.2. アルゴリズム

これで、補助配列Cを使用して入力配列を並べ替えることができます。カウントソートの仕組みは次のとおりです。

入力配列を逆に繰り返します
各要素iについて、 C [i] – 1 は、ソートされた配列内の番号iの位置を表します。これは、 C[i]要素がi以下であるためです。
次に、各ラウンドの終了時に C[i]をデクリメントします

サンプルの入力配列を並べ替えるには、最初に5という数字から始める必要があります。これは、最後の要素だからです。 C [5]によると、には5以下の要素が11個あります。

したがって、5はソートされた配列の11 ^th要素である必要があり、したがってインデックス10は次のようになります。

5をソートされた配列に移動したので、デクリメントする必要があります C[5]。逆順の次の要素は2です。 2以下の要素が4つあるため、この数は、並べ替えられた配列の4 ^th要素である必要があります。

同様に、0である次の要素の適切な場所を見つけることができます。

逆に繰り返し、各要素を適切に移動すると、次のようになります。

3. ソートのカウント–Javaの実装

3.1. 周波数配列の計算

まず、要素の入力配列と kが与えられた場合、配列 C：を計算する必要があります。

int[] countElements(int[] input, int k) {
    int[] c = new int[k + 1];
    Arrays.fill(c, 0);

    for (int i : input) {
        c[i] += 1;
    }

    for (int i = 1; i < c.length; i++) {
	c[i] += c[i - 1];
    }

    return c;
}

メソッドシグネチャを分解してみましょう。

input は、並べ替える数値の配列を表します
入力配列は、[0、 k ]の範囲の整数の配列です。したがって、 k は、入力の最大数を表します。 ]
戻り値の型は、 Carrayを表す整数の配列です。

countElementsメソッドの仕組みは次のとおりです。

まず、Cアレイを初期化しました。 [0、k]の範囲には k + 1 の数値が含まれているため、 k +1の数値を含むことができる配列を作成しています。
次に、入力の数値ごとに、その数値の頻度を計算しています。
そして最後に、連続する要素を一緒に追加して、特定の数以下の要素の数を確認します

また、countElementsメソッドが期待どおりに機能することを確認できます。

@Test
void countElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExpected() {
    int k = 5;
    int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 };
    
    int[] c = CountingSort.countElements(input, k);
    int[] expected = { 1, 2, 4, 6, 8, 11 };
    assertArrayEquals(expected, c);
}

3.2. 入力配列の並べ替え

頻度配列を計算できるようになったので、任意の数値のセットを並べ替えることができるはずです。

int[] sort(int[] input, int k) {
    int[] c = countElements(input, k);

    int[] sorted = new int[input.length];
    for (int i = input.length - 1; i >= 0; i--) {
        int current = input[i];
	sorted[c[current] - 1] = current;
	c[current] -= 1;
    }

    return sorted;
}

sortメソッドの仕組みは次のとおりです。

まず、C配列を計算します
次に、入力配列を逆に繰り返し、入力の各要素について、はソートされた配列内の正しい場所を見つけます。入力のi番目の要素は、ソートされた配列のC[i]番目の要素である必要があります。 Java配列はゼロインデックスであるため、 C [i]-1エントリはC[i]番目の要素です。たとえば、 sorted [5] ソートされた配列の6番目の要素です
一致するものが見つかるたびに、対応する C[i]値がデクリメントされます。

同様に、sortメソッドが期待どおりに機能することを確認できます。

@Test
void sort_GivenAnArray_ShouldSortTheInputAsExpected() {
    int k = 5;
    int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 };

    int[] sorted = CountingSort.sort(input, k);

    // Our sorting algorithm and Java's should return the same result
    Arrays.sort(input);
    assertArrayEquals(input, sorted);
}

4. カウントソートアルゴリズムの再検討

4.1. 複雑さの分析

マージソートなどのほとんどの従来のソートアルゴリズムは、入力要素を相互に比較するだけで、任意の入力をソートします。これらのタイプのソートアルゴリズムは、 比較ソート 。最悪の場合、比較ソートでは、 n 要素をソートするために、少なくともO （n log n）が必要です。

一方、カウントソートは、入力要素を比較して入力をソートしないため、明らかに比較ソートアルゴリズムではありません。

入力の並べ替えにかかる時間を見てみましょう。

O（n + k）時間で C配列を計算します。O（n） O（n）でサイズnの入力配列を一度繰り返します。 X123X]次に、 O（k）–のC を繰り返し、合計で O（n + k）になります。
Cを計算した後、は、入力配列を反復し、各反復でいくつかのプリミティブ操作を実行することにより、入力をソートします。したがって、実際の並べ替え操作には O（n）が必要です。

合計すると、ソートのカウントには O（n + k）の実行時間がかかります。

O(n + k) + O(n) = O(2n + k) = O(n + k)

k = O（n）と仮定すると、カウントソートアルゴリズムは入力を線形時間でソートします。汎用ソートアルゴリズムとは対照的に、カウントソートは入力について仮定し、Oよりも少なくなります。 （n log n）実行の下限。

4.2. 安定

少し前に、ソートのカウントの仕組みについていくつかの固有のルールを設定しましたが、その背後にある理由を明確にすることはありませんでした。もう少し詳しく言うと：

入力配列を逆に繰り返す必要があるのはなぜですか？
使用するたびにC[i] をデクリメントするのはなぜですか？

最初のルールをよりよく理解するために、最初から繰り返してみましょう。次のような整数の単純な配列を並べ替えるとします。

最初の反復では、最初の1のソートされた場所を見つける必要があります。

したがって、番号1の最初の出現は、ソートされた配列の最後のインデックスを取得します。番号0をスキップして、番号1の2番目のオカレンスがどうなるか見てみましょう。

同じ値を持つ要素の出現順序は、入力配列と並べ替えられた配列で異なるため、最初から反復しているとき、アルゴリズムは安定ではありません。

使用するたびにC[i] の値をデクリメントしないとどうなりますか？どれどれ：

番号1の両方のオカレンスは、ソートされた配列の最後の場所を取得しています。したがって、使用するたびに C [i] の値をデクリメントしないと、並べ替え中にいくつかの数値が失われる可能性があります。

5. 結論

このチュートリアルでは、最初に、カウントソートが内部でどのように機能するかを学びました。次に、この並べ替えアルゴリズムをJavaに実装し、その動作を検証するためのテストをいくつか作成しました。そして最後に、アルゴリズムが線形時間計算量を持つ安定ソートアルゴリズムであることを証明しました。

いつものように、サンプルコードは GitHub プロジェクトで入手できますので、ぜひチェックしてください。

getdocs

13036