1. 概要

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

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

ソートアルゴリズムの安定性は、アルゴリズムが等しい（または繰り返される）要素を処理する方法に関係しています。 安定した並べ替えアルゴリズムは等しい要素の相対的な順序を保持しますが、不安定な並べ替えアルゴリズムは保持しません。 言い換えると、安定ソートは、2つの等しい要素の相対的な位置を維持します。

させて A 要素のコレクションであり、< 厳密な弱順序要素に。 さらに、BをAの要素のソート順のコレクションとします。 Aのインデックスiとjの2つの等しい要素、つまり A[i]とA[j ] 、Bのインデックスmとnでそれぞれ終了します。 次の場合、ソートを安定として分類できます。

i < j and A[i] = A[j] and m < n

例を使って概念を理解しましょう。 整数Aの配列があります： [5、8、9、8、3]。 色分けされたボールを使用して配列を表現しましょう。同じ整数の2つのボールは異なる色になり、等しい要素（この場合は8）を追跡するのに役立ちます。 安定した並べ替えでは、8の番号が付けられた2つの等しいボールの順序が維持されますが、不安定な並べ替えでは、2つの8の相対的な順序が逆になる場合があります。

3. 安定性が重要な場合

3.1. 等しい要素を区別する

すべての並べ替えアルゴリズムは、並べ替えキーと呼ばれる、コレクション内の要素の順序を決定するためのキーを使用します。

ソートキーが（全体の）要素自体である場合、整数や文字列などの等しい要素は区別できません。

一方、ソートキーが1つ以上で構成されている場合、等しい要素は区別できますが、Employeeクラスのageなどの要素のすべての属性ではありません。

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

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

  • 等しい要素は区別がつかない、または
  • コレクション内のすべての要素は別個のものです

等しい要素が区別できる場合、安定性が不可欠です。  たとえば、コレクションにすでに何らかの順序がある場合、別のキーで並べ替えると、その順序を保持する必要があります。

たとえば、テキストファイル内の個別の単語の単語数を計算しているとします。 ここで、結果をカウントの降順で報告し、2つの単語のカウントが同じ場合はさらにアルファベット順に並べ替える必要があります。

最初のステップ–単語数を計算します。

Input:

how much wood would woodchuck chuck if woodchuck could chuck wood

Output:

how       1
much      1
wood      2
would     1
woodchuck 2
chuck     2
if        1
could     1

2番目のステップ–リスト全体を辞書式に並べ替えてから、単語数で並べ替えます。

First pass, sorted lexicographically:

(chuck, 2)
(could, 1)
(how, 1)
(if, 1)
(much, 1)
(wood, 2)
(woodchuck, 2)
(would, 1)

Second pass, sorted by count using an unstable sort:

(wood, 2)
(chuck, 2)
(woodchuck, 2)
(could, 1)
(how, 1)
(if, 1)
(would, 1)
(much, 1)

不安定なソートを使用したため、2番目のパスは辞書式順序を維持しません。

そこで、安定ソートが登場します。 リストを辞書式順序で並べ替えたので、単語数による安定した並べ替えを使用しても、等しい要素の順序は変更されなくなりました。その結果、同じ単語数の単語は辞書式順序のままになります。

Second pass, sorted by count using a stable sort:

(chuck, 2)
(wood, 2)
(woodchuck, 2)
(could, 1)
(how, 1)
(if, 1)
(much, 1)
(would, 1)

3.3. 基数ソート

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

基数ソートのサブルーチンとしてCountingSortを使用しています。 カウントソートは、安定した整数ソートアルゴリズムです。 それがどのように機能するかを理解する必要はありませんが、カウントソートは安定しています。

実例を見てみましょう： Counting Sortサブルーチンを呼び出すたびに、前の呼び出しからの順序が保持されます。 たとえば、10桁の数字で並べ替えている間（2回目の呼び出し）、9881は下にシフトしますが、相対的な順序を維持しながら9888より上に留まります。

したがって、基数ソートは、カウントソートアルゴリズムの安定性を利用し、線形時間整数ソートを提供します。

4. 安定および不安定並べ替えアルゴリズム

マージソート、ティムソート、カウントソート、挿入ソート、など、いくつかの一般的なソートアルゴリズムは本質的に安定しています。バブルソート。 クイックソート、ヒープソート、選択ソートなどの他のものは不安定です。

不安定なソートアルゴリズムを変更して安定させることができます。 たとえば、クイックソートの安定性を維持するために余分なスペースを使用できます。

5. 結論

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