1. 概要

このチュートリアルでは、Javaの実装に焦点を当てて、QuickSortアルゴリズムについて詳しく説明します。

また、その長所と短所について説明し、時間計算量を分析します。

2. クイックソートアルゴリズム

クイックソートは、分割統治法を活用した並べ替えアルゴリズムです。 それは平均を持っています O(n log n) 複雑であり、特にビッグデータボリュームで最も使用される並べ替えアルゴリズムの1つです。

クイックソートは安定したアルゴリズムではないことを覚えておくことが重要です。 安定ソートアルゴリズムは、同じ値を持つ要素が、入力リストに表示されるのと同じ順序で、ソートされた出力に表示されるアルゴリズムです。

入力リストは、ピボットと呼ばれる要素によって2つのサブリストに分割されます。 ピボットよりも小さい要素を持つサブリストと、ピボットよりも大きい要素を持つサブリスト。 このプロセスは、サブリストごとに繰り返されます。

最後に、ソートされたすべてのサブリストがマージされて、最終出力が形成されます。

2.1. アルゴリズムの手順

  1. リストからピボットと呼ばれる要素を選択します。 これを使用して、リストを2つのサブリストに分割します。
  2. ピボットの周りのすべての要素を並べ替えます。値が小さい要素はその前に配置され、ピボットよりも大きい要素はすべて後に配置されます。 このステップの後、ピボットは最終位置にあります。 これは重要なパーティションステップです。
  3. 上記の手順を、ピボットの左側と右側の両方のサブリストに再帰的に適用します。

ご覧のとおり、クイックソートは、すべての分割統治アプローチと同様に、当然再帰的なアルゴリズムです。

このアルゴリズムをよりよく理解するために、簡単な例を見てみましょう。

Arr[] = {5, 9, 4, 6, 5, 3}
  1. 簡単にするために5をピボットとして選択するとします。
  2. まず、5未満のすべての要素を配列の最初の位置に配置します:{3、4、5、6、5、9}
  3. 次に、3をピボットとして、左側のサブ配列{3,4}に対してこれを繰り返します。
  4. 3未満の要素はありません
  5. ピボットの右側のサブ配列にクイックソートを適用します。 {4}
  6. このサブ配列は、ソートされた1つの要素のみで構成されます
  7. 最終的に順序付けられた配列を取得するまで、元の配列の右側の部分{6、5、9}を続行します

2.2. 最適なピボットの選択

クイックソートの重要なポイントは、最適なピボットを選択することです。 もちろん、真ん中の要素は、リストを2つの等しいサブリストに分割するので最適です。

ただし、順序付けされていないリストから中央の要素を見つけるのは難しく、時間がかかります。そのため、最初の要素、最後の要素、中央値、またはその他のランダムな要素をピボットとして使用します。

3. Javaでの実装

最初のメソッドはquickSort()で、これはパラメーターとして、ソートされる配列、最初と最後のインデックスを取ります。 まず、インデックスを確認し、並べ替える要素がまだある場合にのみ続行します。

ソートされたピボットのインデックスを取得し、それを使用して、 quickSort()メソッドと同じパラメーターを使用して、 partition()メソッドを再帰的に呼び出しますが、インデックスは異なります。

public void quickSort(int arr[], int begin, int end) {
    if (begin < end) {
        int partitionIndex = partition(arr, begin, end);

        quickSort(arr, begin, partitionIndex-1);
        quickSort(arr, partitionIndex+1, end);
    }
}

partition()メソッドを続けましょう。 簡単にするために、この関数は最後の要素をピボットとして使用します。 次に、各要素をチェックし、その値が小さい場合はピボットの前に交換します。

パーティショニングの終わりまでに、ピボットよりも小さいすべての要素がその左側にあり、ピボットよりも大きいすべての要素がその右側にあります。 ピボットは最終的にソートされた位置にあり、関数はこの位置を返します。

private int partition(int arr[], int begin, int end) {
    int pivot = arr[end];
    int i = (begin-1);

    for (int j = begin; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;

            int swapTemp = arr[i];
            arr[i] = arr[j];
            arr[j] = swapTemp;
        }
    }

    int swapTemp = arr[i+1];
    arr[i+1] = arr[end];
    arr[end] = swapTemp;

    return i+1;
}

4. アルゴリズム分析

4.1. 時間計算量

最良の場合、アルゴリズムはリストを2つの等しいサイズのサブリストに分割します。 したがって、完全な n サイズのリストの最初の反復には、 O(n)が必要です。 残りの2つのサブリストをn/ 2 要素で並べ替えると、それぞれ 2 * O(n / 2)かかります。 その結果、QuickSortアルゴリズムの複雑さは O(n log n)になります。

最悪の場合、アルゴリズムは各反復で1つの要素のみを選択するため、 O(n)+ O(n-1)+…+ O(1)は、Oと等しくなります。 (n2)

平均して、QuickSortは O(n log n)の複雑さを持っているため、ビッグデータボリュームに適しています。

4.2. クイックソートとマージソート

マージソートではなくクイックソートを選択する必要がある場合について説明しましょう。

クイックソートとマージソートはどちらも平均時間計算量がO(n log n)ですが、 O(log(n)) があるため、クイックソートが推奨されるアルゴリズムです。スペースの複雑さ。 一方、Mergesortは、 O(n)の追加ストレージを必要とするため、アレイのコストが非常に高くなります。

クイックソートは、その操作のためにさまざまなインデックスにアクセスする必要がありますが、連続ブロックがないため、このアクセスはリンクリストでは直接可能ではありません。 したがって、要素にアクセスするには、リンクリストの先頭から各ノードを反復処理する必要があります。 また、Mergesortは、LinkedLists。用の余分なスペースなしで実装されます。

このような場合、クイックソートとマージソートのオーバーヘッドの増加が一般的に好まれます。

5. 結論

クイックソートは、ほとんどの場合に非常に役立つ洗練された並べ替えアルゴリズムです。

これは一般に「インプレース」アルゴリズムであり、平均時間計算量は O(n log n)です。

言及すべきもう1つの興味深い点は、Javaの Arrays.sort()メソッドは、プリミティブの配列をソートするためにクイックソートを使用することです。 実装は2つのピボットを使用し、単純なソリューションよりもはるかに優れたパフォーマンスを発揮します。そのため、本番コードでは通常、ライブラリメソッドを使用する方が適切です。

いつものように、このアルゴリズムを実装するためのコードは、GitHubリポジトリにあります。