Javaでのソートのカウント

1. 概要

link:/java-merge-sort[Merge Sort]のような汎用ソートアルゴリズムは、入力に関する仮定を行わないため、最悪の場合_O(n log n)_に勝てません。 反対に、並べ替えのカウントでは、入力に関する仮定があり、線形時間並べ替えアルゴリズムになります。
このチュートリアルでは、Counting Sortの仕組みを理解し、Javaで実装します。

2. ソート順

ほとんどの古典的な並べ替えアルゴリズムとは対照的に、カウントの並べ替えは、要素を比較することによって指定された入力を並べ替えません。 代わりに、入力要素が[0、_k _] *の範囲の_n_ integersであると仮定します。 __k = O(n)、__thenの場合、カウントソートは_O(n)_時間で実行されます。
したがって、カウントソートを汎用のソートアルゴリズムとして使用することはできません。 ただし、入力がこの仮定に沿っている場合、非常に高速です!

2.1. 周波数アレイ

 入力array__ __の値を次の値でソートするとします。
[0, 5] range:link:/uploads/counts.png[ +
 ]
link:/uploads/To-Sort-Array-100x9.png%20100w []
まず、*入力配列内の各数値の出現をカウントする必要があります。 配列_C_でカウントを表す場合、__C [i] __は、入力配列*の数値の頻度__i __を表します。
link:/uploads/counts-100x24.png%20100w []
たとえば、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 __consecutive要素の合計を計算し続けると、___は入力配列のnumber _n-1_以下の要素の数を知ることができます。 **とにかく、この単純な式を適用することにより、__C __を次のように更新できます。
    link:/uploads/less-than.png []

2.2. アルゴリズム

これで、補助配列__C ___を使用して入力配列をソートできます。 カウントソートの仕組みは次のとおりです。
  • 入力配列を逆に繰り返します

  • 各要素についてi、C [i] – 1 は番号の位置を表します_i_
    ソートされた配列。 これは、C [i] element要素が__i_以下であるためです。

  • 次に、各ラウンドの終わりにC [i] をデクリメントします

    サンプルの入力配列をソートするには、最後の要素であるため、最初に5から開始する必要があります。 __C [5]によると、___は11個の要素が5以下であるということです。
    したがって、5はソートされた配列の11 ^ th ^要素である必要があり、したがってインデックス10です。
    link:/uploads/Untitled-Diagram-100x22.png%20100w []
    5をソートされた配列に移動したので、__C [5]を減らす必要があります。 逆順の__Next要素は2です。 2以下の要素が4つあるため、この数は、ソートされた配列の4番目の要素である必要があります。
    link:/uploads/Untitled-Diagram-1-100x22.png%20100w []
    同様に、次の要素0の正しい場所を見つけることができます。
    link:/uploads/Untitled-Diagram-2-100x22.png%20100w []
    逆に繰り返して各要素を適切に移動すると、次のような結果になります。
    link:/uploads/Untitled-Diagram-3-100x11.png%20100w []

3. カウントソート-Java実装

3.1. 周波数配列の計算

まず、要素の入力配列と__kが与えられた場合、___配列を計算する必要がありますshould_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 reは、ソートする数値の配列を表します

  • input_配列は、[0、_k]の範囲の整数の配列です–
    したがって、 k は、_input_の最大数を表します

  • 戻り値の型は、C _arrayを表す整数の配列です。

    そして、これが__countElements __methodの仕組みです:
  • まず、C arrayを初期化しました。 [0、k]範囲として
    contains k 1 numbers、wek 1 numbersを含むことができる配列を作成しています

  • 次に、inputの各数値について、_は周波数を計算しています
    その数の

  • そして最後に、連続する要素を一緒に追加して、
    多くの要素が特定の数以下である

    また、__countElements ___methodが期待どおりに機能することを確認できます。
@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 ___methodの仕組みは次のとおりです。
  • 最初に、C arrayを計算します

  • 次に、 input arrayを逆に、各要素に対して繰り返します
    inputで、はソートされた配列内の正しい場所を見つけます。 input _のi ^ th ^ elementは、ソートされた配列のC [i] ^ th ^ elementでなければなりません。 Java配列はゼロインデックスであるため、_C [i] -1_エントリはentry C [i] ^ th ^ elementです。たとえば、 sorted [5] はソートされた配列の6番目の要素です。

  • 一致が見つかるたびに、対応する
    C [i] value

    同様に、__sort ___methodが期待どおりに機能することを確認できます。
@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. 複雑性分析

  • https://www.baeldung.com/java-merge-sort [merge sort]などのほとんどの古典的なソートアルゴリズムは、入力要素を相互に比較するだけで任意の入力をソートします。 **これらの種類のソートアルゴリズムは、_comparison sorts_として知られています。 最悪の場合、比較ソートでは、 n elementsをソートするために少なくともO (n log n)が必要です。

    一方、ソートをカウントすると、入力要素を比較して入力がソートされることはないため、比較ソートアルゴリズムではないことは明らかです。
    入力をソートするのにどれだけ時間がかかるか見てみましょう:
    • これは、O(n k)timeでC arrayを計算します。
      サイズがn in O(n)の入力配列。次に、C in _O(k)–_を繰り返し、合計でO(n k)inになる

    • Cを計算した後、itは入力を反復することで入力をソートします
      各反復で配列といくつかのプリミティブ操作を実行します。 したがって、実際のソート操作には_O(n)_

      合計で、ソートのカウントには実行に__O(n k)___時間がかかります。
O(n + k) + O(n) = O(2n + k) = O(n + k)
  • k = O(n)と仮定すると、thenカウントソートアルゴリズムは入力を線形時間でソートします。*汎用ソートアルゴリズムとは対照的に、カウントソートは入力について仮定し、O (n log n )lower実行の下限。

4.2. 安定

少し前に、ソートのカウントの仕組みに関するいくつかの独特なルールを作成しましたが、その背後にある理由を明確にしませんでした。 具体的には:
  • 入力配列を逆に繰り返す必要があるのはなぜですか?

  • 使用するたびにC [i] を減らすのはなぜですか?

    最初から繰り返して、最初のルールをよりよく理解しましょう。 次のような整数の単純な配列をソートするとします。
    link:/uploads/Untitled-Diagram-4-100x36.png%20100w []
    最初の反復では、最初の1のソートされた場所を見つける必要があります。
    link:/uploads/Untitled-Diagram-5-100x76.png%20100w []
    したがって、番号1の最初の出現は、ソートされた配列の最後のインデックスを取得します。 番号0をスキップして、番号1の2回目の出現で何が起こるか見てみましょう。
    link:/uploads/Untitled-Diagram-6-100x76.png%20100w []
    *同じ値を持つ要素の出現順序は入力配列とソートされた配列で異なるため、最初から反復するときのアルゴリズムはlink:/stable-sorting-algorithms[stable]ではありません。*
    各使用後に__C [i] ___valueを減らさないとどうなりますか? どれどれ:
    link:/uploads/Untitled-Diagram-2-1-100x42.png%20100w []
    番号1の両方の出現は、ソートされた配列の最後の場所を取得しています。 したがって、使用するたびに__C [i] __valueを減らさないと、ソート中にいくつかの数字が失われる可能性があります!

5. 結論

このチュートリアルでは、まず、カウントソートが内部でどのように機能するかを学びました。 次に、このソートアルゴリズムをJavaで実装し、その動作を検証するためのテストをいくつか作成しました。 そして最後に、アルゴリズムが線形時間の複雑さを持つ安定したソートアルゴリズムであることを証明しました。
いつものように、サンプルコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[GitHub]プロジェクトで入手できるので、ぜひチェックしてください。