安定したソートアルゴリズム

1.  概要

このチュートリアルでは、安定したソートアルゴリズムとは何か、そしてそれらがどのように機能するかを学びます。 さらに、並べ替えの安定性が重要な場合を検討します。

2. ソートアルゴリズムの安定性

ソートアルゴリズムの安定性は、*アルゴリズムが等しい(または繰り返される)要素を処理する方法*に関係しています。 安定したソートアルゴリズムは等しい要素の相対的な順序を保持しますが、不安定なソートアルゴリズムは保持しません。 言い換えると、安定したソートでは、2つの等しい要素の位置が互いに相対的に維持されます。
_A_を要素のコレクションとし、<を要素のhttps://www.boost.org/sgi/stl/StrictWeakOrdering.html[strict weak ordering]とします。 さらに、_B_を_A_内の要素のコレクションをソートされた順にします。 インデックス_i_と_j_の_A_の2つの等しい要素、つまり、_B_のインデックス_m_と_n_で終わる_A [i] _と_A [j] _を考えてみましょう。 次の場合、ソートを安定したものとして分類できます。
i < j and A[i] = A[j] and m < n
例の助けを借りて概念を理解しましょう。 整数Aの配列があります:__ [_5、8、9、8、3_] _。 色分けされたボールを使用して配列を表現しましょう。同じ整数の2つのボールは、同じ要素(この場合は8)を追跡するのに役立つ異なる色になります:link:/uploads /Stable-vs-Unstable-1-100x28.png%20100w []安定した並べ替えでは8番の2つの等しいボールの順序が維持されますが、不安定な並べ替えでは2つの8の相対的な順序が逆になる場合があります。

3. 安定性が重要な場合

3.1. 等しい要素の区別

すべてのソートアルゴリズムは、_sort key_と呼ばれるキーを使用して、コレクション内の要素の順序を決定します。
ソートキーが(全体の)要素自体である場合、整数や文字列などの等しい要素は区別できません。
一方、並べ替えキーが1つ以上の要素で構成されている場合、等しい要素は区別できますが、_age_ in an _Employee_クラスなど、要素のすべての属性ではありません。

3.2. 安定したソートが重要な場合があります

常に安定したソートが必要なわけではありません。 次の場合、安定性は問題になりません。
  • 等しい要素が区別できない、または

  • コレクション内のすべての要素は明確です

    等しい要素が区別できる場合、安定性が不可欠です*。 たとえば、コレクションにすでに何らかの順序がある場合、別のキーでのソートはその順序を保持する必要があります。
    たとえば、テキストファイル内の個々の単語の単語数を計算しているとします。 次に、カウントの降順で結果を報告し、2つの単語のカウントが同じ場合にアルファベット順にさらにソートする必要があります。
Input:
how much wood would woodchuck chuck if woodchuck could chuck wood

Output:
chuck       2
wood        2
woodchuck   2
could       1
how         1
if          1
much        1
would       1
カウントで要素を並べ替えたら、辞書順でさらに並べ替える必要があります。 この時点で、ソートアルゴリズムはカウントの相対的な順序を維持する必要があります。
First pass, sorted by count:
(wood, 2)
(chuck, 2)
(woodchuck, 2)
(much, 1)
(could, 1)
(would, 1)
(if, 1)
(how, 1)

Second pass, sorted lexicographically while preserving the previous relative order:
(chuck, 2)
(wood, 2)
(woodchuck, 2)
(could, 1)
(how, 1)
(if, 1)
(much, 1)
(would, 1)

3.3. 基数ソート

https://brilliant.org/wiki/radix-sort/[Radix Sort]は、*安定している必要があるソートサブルーチンに依存する*整数ソートアルゴリズムです。 これは、整数のコレクションをソートする非比較ベースのソートアルゴリズムです。 同じ重要な位置と値を共有する個々の数字でキーをグループ化します。
正式な定義を展開して、基本的な考え方をもう一度説明しましょう。
for each digit 'k' from the least significant digit (LSD) to the most significant digit (MSD) of a number:
  apply counting-sort algorithm on digit 'k' to sort the input array
Radix Sortのサブルーチンとしてhttps://brilliant.org/wiki/counting-sort/[Counting Sort]を使用しています。 カウントソートは、安定した整数ソートアルゴリズムです。 どのように機能するかを理解する必要はありませんが、* Counting Sortは安定しています*。
説明的な例を見てみましょう:link:/uploads/radix-stable-100x44.png%20100w [] Counting Sortサブルーチンの各呼び出しは、前の呼び出しからの順序を保持します。 たとえば、10の位の桁でのソート(2回目の呼び出し)9881は下方にシフトしますが、相対的な順序を維持して9888を超えたままになります。
したがって、Radix SortはCounting Sortアルゴリズムの安定性を利用し、線形時間整数ソートを提供します。

4. 安定および不安定*選別アルゴリズム*

link:/java-merge-sort[Merge Sort]、https://docs.oracle.com/javase/8/docs/api/javaなど、いくつかの一般的なソートアルゴリズムは本質的に安定しています。 /util/Arrays.html#sort-java.lang.Object:A-[Timsort]、https://brilliant.org/wiki/counting-sort/[Counting Sort]、link:/ java-insertion-sort [Insertion Sort]、およびlink:/java-bubble-sort[Bubble Sort]。 link:/java-quicksort[Quicksort]、link:/java-heap-sort[Heapsort]、link:/javaなど-selection-sort [Selection Sort]は不安定です。
不安定なソートアルゴリズムを修正して、安定させることができます。 たとえば、Quicksortの安定性を維持するために余分なスペースを使用できます。

5.  結論

このチュートリアルでは、基数ソートを例として使用して、安定したソートアルゴリズムについて学習し、安定性が重要な場合を検討しました。