1. 概要

アルゴリズムの実行時の複雑さは、多くの場合、入力の性質に依存します。

このチュートリアルでは、クイックソートアルゴリズムの簡単な実装では、繰り返される要素のパフォーマンスがどのように低下するかを確認します。

さらに、高密度の重複キーを使用して入力を効率的に分割およびソートするためのいくつかのクイックソートバリアントを学習します。

2. ささいなクイックソート

Quicksort は、分割統治パラダイムに基づく効率的な並べ替えアルゴリズムです。 機能的に言えば、は入力配列上でインプレースで動作し、単純な比較およびスワップ操作で要素を再配置します。

2.1. シングルピボットパーティショニング

クイックソートアルゴリズムの簡単な実装は、シングルピボットパーティショニング手順に大きく依存しています。 つまり、パーティショニングにより、配列A = [a p 、a p + 1 、a p + 2 、…、a r[が分割されます。 X101X]]をA[p..q]とA[q+1..r]の2つの部分に分割します。

  • 最初のパーティションA[p..q]のすべての要素は、ピボット値A[q]以下です。
  • 2番目のパーティションA[q + 1..r]のすべての要素は、ピボット値A[q]以上です。

その後、2つのパーティションは独立した入力配列として扱われ、Quicksortアルゴリズムに送られます。 Lomutoのクイックソートの動作を見てみましょう。

2.2. 繰り返される要素によるパフォーマンス

すべて等しい要素を持つ配列A=[4、4、4、4、4、4、4、4]があるとします。

この配列をシングルピボットパーティションスキームでパーティション化すると、2つのパーティションが取得されます。 最初のパーティションは空になり、2番目のパーティションにはN-1個の要素が含まれます。 さらに、パーティションプロシージャを呼び出すたびに、入力サイズが1つだけ減少します。 それがどのように機能するか見てみましょう：

分割手順には線形の時間計算量があるため、この場合、全体的な時間計算量は2次式になります。 これは、入力配列の最悪のシナリオです。

3. スリーウェイパーティショニング

繰り返されるキーの数が多い配列を効率的にソートするために、より責任を持って等しいキーを処理することを選択できます。 アイデアは、私たちが最初にそれらに遭遇したときにそれらを正しい位置に配置することです。 したがって、私たちが探しているのは、配列の3つのパーティションの状態です。

  • 左端のパーティションには、パーティションキーよりも厳密に小さい要素が含まれています
  • The 中央のパーティションには、パーティションキーと等しいすべての要素が含まれています
  • 右端のパーティションには、パーティションキーよりも厳密に大きいすべての要素が含まれています

次に、3者間分割を実現するために使用できるいくつかのアプローチについて詳しく説明します。

4. ダイクストラのアプローチ

ダイクストラのアプローチは、3者間分割を行うための効果的な方法です。 これを理解するために、古典的なプログラミングの問題を調べてみましょう。

4.1. オランダ国家旗問題

オランダのトリコロール旗に触発されて、 Edsger Dijkstra は、 Dutch National Flag Problem （DNF）と呼ばれるプログラミング問題を提案しました。

一言で言えば、それは再配置の問題であり、3色のボールがランダムに一列に並べられ、同じ色のボールをグループ化するように求められます。 さらに、再配置では、グループが正しい順序に従うようにする必要があります。

興味深いことに、DNFの問題は、繰り返される要素を持つ配列の3方向の分割と非常によく似ています。

配列のすべての番号を、特定のキーに関して3つのグループに分類できます。

  • 赤のグループには、キーよりも厳密に小さいすべての要素が含まれています
  • ホワイトグループには、キーと等しいすべての要素が含まれています
  • ブルーグループには、キーよりも厳密に大きいすべての要素が含まれています

4.2. アルゴリズム

DNFの問題を解決するためのアプローチの1つは、最初の要素をパーティショニングキーとして選択し、アレイを左から右にスキャンすることです。 各要素をチェックするときに、それを正しいグループ、つまり、Lesser、Equal、およびGreaterに移動します。

パーティショニングの進行状況を追跡するには、3つのポインタの助けが必要です。 lt 、 現在 、 と gt。 どの時点でも、ltの左側の要素はパーティショニングキーよりも厳密に小さくなり、gtの右側の要素はキーよりも厳密に大きくなります。 。

さらに、スキャンには current ポインターを使用します。これは、currentポインターとgtポインターの間にあるすべての要素がまだ探索されていないことを意味します。

まず、ltおよびcurrentポインターを配列の最初に設定し、gtポインターを配列の最後に設定できます。

current ポインターを介して読み取られた要素ごとに、それをパーティション化キーと比較し、次の3つの複合アクションのいずれかを実行します。

  • もしも input[current]<キー 、その後交換します入力電流] と input [lt] 両方をインクリメントします現在と lt ポインタ
  • input [current] == key の場合、currentポインターをインクリメントします
  • input [current]> key の場合、 input[current]とinput[gt] を交換し、gtをデクリメントします。

最終的に、現在のポインターとgtポインターが互いに交差したときに停止します。 これにより、未探索領域のサイズがゼロになり、必要なパーティションは3つだけになります。

最後に、このアルゴリズムが重複する要素を持つ入力配列でどのように機能するかを見てみましょう。

4.3. 実装

まず、 compare（）という名前のユーティリティプロシージャを記述して、2つの数値を3者間で比較します。

public static int compare(int num1, int num2) {
    if (num1 > num2)
        return 1;
    else if (num1 < num2)
        return -1;
    else
        return 0;
}

次に、 swap（）というメソッドを追加して、同じ配列の2つのインデックスで要素を交換しましょう。

public static void swap(int[] array, int position1, int position2) {
    if (position1 != position2) {
        int temp = array[position1];
        array[position1] = array[position2];
        array[position2] = temp;
    }
}

配列内のパーティションを一意に識別するには、その左右の境界インデックスが必要です。 それでは、先に進んでPartitionクラスを作成しましょう。

public class Partition {
    private int left;
    private int right;
}

これで、3方向の partition（）プロシージャを作成する準備が整いました。

public static Partition partition(int[] input, int begin, int end) {
    int lt = begin, current = begin, gt = end;
    int partitioningValue = input[begin];

    while (current <= gt) {
        int compareCurrent = compare(input[current], partitioningValue);
        switch (compareCurrent) {
            case -1:
                swap(input, current++, lt++);
                break;
            case 0:
                current++;
                break;
            case 1:
                swap(input, current, gt--);
                break;
        }
    }
    return new Partition(lt, gt);
}

最後に、3ウェイパーティショニングスキームを利用して左右のパーティションを再帰的にソートする quicksort（）メソッドを作成しましょう：

public static void quicksort(int[] input, int begin, int end) {
    if (end <= begin)
        return;

    Partition middlePartition = partition(input, begin, end);

    quicksort(input, begin, middlePartition.getLeft() - 1);
    quicksort(input, middlePartition.getRight() + 1, end);
}

5. ベントレー-マキロイのアプローチ

JonBentleyとDouglasMcIlroy は、最適化バージョンのQuicksortアルゴリズムを共同執筆しました。 このバリアントを理解してJavaに実装しましょう。

5.1. パーティションスキーム

アルゴリズムの核心は、反復ベースのパーティショニングスキームです。 最初は、数字の配列全体が私たちにとって未踏の領域です。

次に、配列の要素を左右の方向から探索し始めます。 探索のループに出入りするときはいつでも、アレイを5つの領域の構成として視覚化できます：

  • 極端な両端には、パーティショニング値に等しい要素を持つ領域があります
  • 未探索の領域は中央にとどまり、そのサイズは反復ごとに縮小し続けます
  • 未踏の領域の左側には、パーティショニング値よりも小さいすべての要素があります
  • 未踏の領域の右側には、パーティショニング値より大きい要素があります

最終的に、探索する要素がなくなると、探索のループは終了します。 この段階では、未探索領域のサイズは事実上ゼロであり、残りの領域は4つだけです。

次に、中央の2つの等しい領域からすべての要素を移動し、左側の小さい領域と大きい領域で囲まれた中央に等しい領域が1つだけになるようにします。右。 そのためには、まず、左側の等領域の要素を、より少ない領域の右端の要素と交換します。 同様に、右側の等しい領域の要素は、大きい領域の左端の要素と交換されます。

最後に、 3つのパーティションだけが残り、同じアプローチを使用して、より少ない領域とより大きな領域をさらに分割できます。

5.2. 実装

スリーウェイクイックソートの再帰的な実装では、下限と上限のセットが異なるサブ配列に対してパーティションプロシージャを呼び出す必要があります。 したがって、 partition（）メソッドは、3つの入力、つまり配列とその左および右の境界を受け入れる必要があります。

public static Partition partition(int input[], int begin, int end){
	// returns partition window
}

簡単にするために、配列の最後の要素としてパーティショニング値を選択できます。 また、2つの変数 left =beginとright= end を定義して、配列を内側に探索しましょう。

さらに、左端と右端にある等しい要素の数を追跡する必要もあります。 それでは、 leftEqualKeysCount =0とrightEqualKeysCount= 0 を初期化して、アレイを探索してパーティション化する準備が整いました。

まず、両方向から移動を開始し、反転を見つけます。ここで、左側の要素は分割値以上であり、右側の要素は分割値以下です。 次に、左右の2つのポインターが交差していない限り、2つの要素を交換します。

各反復で、 partitioningValue に等しい要素を両端に向かって移動し、適切なカウンターをインクリメントします。

while (true) {
    while (input[left] < partitioningValue) left++; 
    
    while (input[right] > partitioningValue) {
        if (right == begin)
            break;
        right--;
    }

    if (left == right && input[left] == partitioningValue) {
        swap(input, begin + leftEqualKeysCount, left);
        leftEqualKeysCount++;
        left++;
    }

    if (left >= right) {
        break;
    }

    swap(input, left, right);

    if (input[left] == partitioningValue) {
        swap(input, begin + leftEqualKeysCount, left);
        leftEqualKeysCount++;
    }

    if (input[right] == partitioningValue) {
        swap(input, right, end - rightEqualKeysCount);
        rightEqualKeysCount++;
    }
    left++; right--;
}

次のフェーズでは、中央の両端からすべての等しい要素を移動する必要があります。 ループを終了すると、左ポインターはpartitioningValue以上の値を持つ要素になります。 この事実を使用して、等しい要素を両端から中央に向かって移動し始めます。

right = left - 1;
for (int k = begin; k < begin + leftEqualKeysCount; k++, right--) { 
    if (right >= begin + leftEqualKeysCount)
        swap(input, k, right);
}
for (int k = end; k > end - rightEqualKeysCount; k--, left++) {
    if (left <= end - rightEqualKeysCount)
        swap(input, left, k);
}

最後のフェーズでは、中間パーティションの境界を返すことができます。

return new Partition(right + 1, left - 1);

最後に、サンプル入力での実装のデモンストレーションを見てみましょう。

6. アルゴリズム分析

一般に、クイックソートアルゴリズムの平均時間計算量はO（n * log（n））であり、最悪の場合の時間計算量はO（n 2 ）です。 重複キーが高密度であるため、Quicksortの簡単な実装で、ほとんどの場合、最悪の場合のパフォーマンスが得られます。

ただし、DNFパーティショニングやBentleyのパーティショニングなど、クイックソートの3ウェイパーティショニングバリアントを使用すると、重複キーの悪影響を防ぐことができます。 さらに、重複キーの密度が高くなると、アルゴリズムのパフォーマンスも向上します。 その結果、すべてのキーが等しい場合に最良のパフォーマンスが得られ、線形時間ですべての等しいキーを含む単一のパーティションが得られます。

それでも、些細なシングルピボットパーティショニングからスリーウェイパーティショニングスキームに切り替えると、基本的にオーバーヘッドが追加されることに注意する必要があります。

DNFベースのアプローチの場合、オーバーヘッドは繰り返されるキーの密度に依存しません。 したがって、すべての一意のキーを持つ配列にDNFパーティショニングを使用すると、ピボットを最適に選択する簡単な実装と比較して、パフォーマンスが低下します。

しかし、Bentley-McIlroyのアプローチは、2つの極端な端から等しいキーを移動するオーバーヘッドがそれらの数に依存するため、賢明なことを行います。 その結果、すべての一意のキーを持つ配列にこのアルゴリズムを使用すると、それでもかなり良好なパフォーマンスが得られます。

要約すると、シングルピボットパーティショニングアルゴリズムとスリーウェイパーティショニングアルゴリズムの両方の最悪の場合の時間計算量は、 O（nlog（n））です。 ただし、の真のメリットは、ベストケースシナリオで確認できます。このシナリオでは、時間計算量がシングルピボットパーティショニングの O（nlog（n））からになります。 O（n）は、3方向のパーティショニング用です。

7. 結論

このチュートリアルでは、入力に多数の繰り返し要素がある場合のクイックソートアルゴリズムの簡単な実装に関するパフォーマンスの問題について学習しました。

この問題を修正する動機を持って、さまざまな3方向パーティショニングスキームと、それらをJavaで実装する方法を学びました。

いつものように、この記事で使用されているJava実装の完全なソースコードは、GitHubで入手できます。