クイックソートアルゴリズムの概要

1. 序章

このチュートリアルでは、クイックソートアルゴリズムを見て、それがどのように機能するかを理解します。

クイックソートは分割統治アルゴリズムです。 つまり、各反復は、入力を2つの部分に分割し、それらを結合する前にを並べ替えることによって機能します。

もともとはTonyHoareによって開発され、1961年に公開されましたが、今でも利用可能なより効率的な汎用ソートアルゴリズムの1つです。

2. アルゴリズム要件

クイックソートアルゴリズムを使用するための唯一の実際の要件は、2つの要素を比較するための明確に定義された操作です。 ある要素が別の要素よりも厳密に小さいかどうかを判断できます。 この比較の正確な性質は、一貫している限り重要ではありません。 直接の等式比較は必要ではなく、比較よりも少ないだけであることに注意してください。

多くのタイプにとって、これは否定できない比較です。 たとえば、数値はこれを行う方法を暗黙的に定義します。 他のタイプはそれほど明白ではありませんが、ソートの要件に基づいてこれを定義することはできます。 たとえば、文字列を並べ替えるときは、大文字と小文字が重要かどうか、またはUnicode文字がどのように機能するかを決定する必要があります。

3. 二分木ソート

Binary Tree Sortは、並べ替える要素で構成されるバランスの取れたバイナリツリーを構築するアルゴリズムです。 これができたら、このツリーから結果を作成できます。

ツリー上のノードとしてピボットを選択し、ノードの左または右ブランチのいずれかにすべての要素を割り当てるという考え方です。それらはピボット要素よりも小さいかどうかです。 次に、完全にソートされたツリーができるまで、これらのブランチを再帰的にソートできます。

3.1. 実施例

たとえば、番号のリスト「3 7 8 5 2 1 9 5 4」を並べ替える場合、最初のパスは次のようになります。

Input: 3 7 8 5 2 1 9 5 4
Pivot = 3
Left = 2 1
Right = 7 8 5 9 5 4Copy

これにより、元の入力から2つのパーティションが得られました。 左側のリストにあるものはすべてピボットよりも厳密に少なく、その他はすべて右側のリストにあります。

次に、同じアルゴリズムを使用してこれら2つのリストを並べ替えます。

Input: 2 1
Pivot = 2
Left = 1
Right = Empty

Input: 7 8 5 9 5 4
Pivot = 7
Left = 5 5 4
Right = 8 9Copy

最初のパスから左側のパーティションを並べ替えると、長さが1以下の2つのリストになりました。 ソートされていないサイズ1のリストを作成することは不可能であるため、これらはすでにソートされています。 これは、ここで停止し、代わりに適切なパーティションの残りの部分に焦点を当てることができることを意味します。

この時点で、次の構造になっています。

      / [1]
    2
  /   \ []
3
  \   / [5 5 4]
    7
      \ [8 9]Copy

ソートされたリストにすでに近づいていることがわかります。 並べ替えるパーティションがさらに2つあり、完了です。

        1
      /
    2       4
  /       /
3       5
  \   /   \
    7       5
      \ 
        8
          \
            9Copy

これにより、アルゴリズムの5つのパスでリストが並べ替えられ、ますます小さくなるサブリストに適用されます。 ただし、メモリの必要性は比較的高く、元のリストの9つの要素を並べ替えるために、さらに17要素に相当するメモリを割り当てる必要がありました。

4. クイックソートの一般的なアイデア

クイックソートアルゴリズムは、概念的にはバイナリツリーソートに似ています。 並べ替える必要がある各ステップでサブリストを作成するのではなく、元のリスト内のすべてを適切に実行します。

選択したピボットの周りのリスト内の要素を動的に交換し、次にこのピボットのいずれかの側にサブリストを再帰的に並べ替えることによって機能します。 これにより、スペース効率が大幅に向上します。これは、巨大なリストにとって重要になる可能性があります。

クイックソートは、ピボットの選択とパーティション化要素のメカニズムという2つの重要な要素に依存します。

このアルゴリズムの鍵はパーティション関数です。これについてはすぐに説明します。 これにより、このインデックスの下のすべての要素がこのインデックスの要素よりも少なくソートされ、このインデックスの要素がその上のすべての要素よりも少なくソートされるように、入力配列にインデックスが返されます。

これを行うには、配列内のいくつかの要素を交換して、これらがこのインデックスの適切な側になるようにする必要があります。

このパーティショニングが完了したら、このインデックスの両側にある2つのパーティションにアルゴリズムを適用します。 これは、それぞれ1つの要素のみを含むパーティションがある場合に最終的に終了し、その時点で入力配列が並べ替えられます。

その結果、クイックソートアルゴリズムを次の3つのステップで要約できます。

1. 要素をピボットとして選択
2. Partition 小さな要素をピボットの左側に移動し、大きな要素をピボットの右側に移動することによって設定される問題
3. 各パーティションで上記の手順を繰り返します

5. クイックソートの例

ここに、クイックソートを使用してソートする10個のソートされていない値の配列があります。

最初のステップは、この配列からピボットとして要素を選択することです。さまざまな方法でピボットを選択できますが、この例では、常に右端の要素を選択します。配列。これは番号5です。

ピボットとして5を決定したので、5より大きい数値を右に、5より小さい数値を左に配置して、ピボットに基づいて配列を分割しましょう。 この時点では、番号の順序についてはあまり心配していません。ピボットに関して適切な場所に移動しただけです。

これを行う際に、ピボット5の周りでアレイを2つの部分に分割しました。

左端のパーティション（インデックス0 – 1）を取得して、手順を繰り返します。 ピボットとして2番を選択し、それに応じて再配置します。これにより、次のようになります。

次に、右端のパーティション（インデックス3〜9）を取得し、10をピボットとして使用します。 10より大きい数字は右側に移動し、10より小さい数字は左側に移動します。

6. クイックソートの実装

クイックソートアルゴリズムには複数の実装があります。 これらの実装は、ピボット要素の選択方法に関して互いに異なります。 分割方法について説明しましょう。

6.1. Lomutoパーティショニング

LomutoPartitioningはNicoLomutoによるものです。 これは、入力配列を反復処理し、事前に選択されたピボット要素よりも厳密に少ない要素を交換することで機能します。 それらは配列の早い段階で表示されますが、スライディングターゲットインデックスに表示されます 。

このスライディングターゲットインデックスは、より大きなアルゴリズムの次の再帰で使用するために返す新しいパーティションインデックスです。

これは、スライドするターゲットインデックスが、配列内でその前にあるすべての要素がこの要素よりも小さくなり、この要素が配列内でそれよりも後のすべての要素よりも小さくなるような位置にあることを確認するためです。

これを擬似コードで見てみましょう。

fun quicksort(input : T[], low : int, high : int) 
    if (low < high) 
        p := partition(input, low, high) 
        quicksort(input, low, p - 1) 
        quicksort(input, p + 1, high)

fun partition(input: T[], low: int, high: int) : int
    pivot := input[high]
    partitionIndex := low
    loop j from low to (high - 1)
        if (input[j] < pivot) then
            swap(input[partitionIndex], input[j])
            partitionIndex := partitionIndex + 1
    swap(input[partitionIndex], input[high]
    return partitionIndex
Copy

実例として、以前の配列を分割できます。

Sorting input: 3,7,8,5,2,1,9,5,4 from 0 to 8
Pivot: 4
Partition Index: 0

When j == 0 => input[0] == 3 => Swap 3 for 3 => input := 3,7,8,5,2,1,9,5,4, partitionIndex := 1
When j == 1 => input[1] == 7 => No Change
When j == 2 => input[2] == 8 => No Change
When j == 3 => input[3] == 5 => No Change
When j == 4 => input[4] == 7 => Swap 7 for 2 => input := 3,2,8,5,7,1,9,5,4, partitionIndex := 2
When j == 5 => input[5] == 8 => Swap 8 for 1 => input := 3,2,1,5,7,8,9,5,4, partitionIndex := 3
When j == 6 => input[6] == 9 => No Change
When j == 7 => input[7] == 5 => No Change

After Loop => Swap 4 for 5 => input := 3,2,1,4,7,8,9,5,5, partitionIndex := 3Copy

これを実行すると、3つのスワップを実行し、インデックス「3」の新しいパーティションポイントを決定したことがわかります。 これらのスワップ後の配列は、要素0、1、および2がすべて要素3未満であり、要素3が要素4、5、6、7、および8よりも小さいようなものです。

これを実行すると、より大きなアルゴリズムが繰り返され、サブ配列が0から2に、サブ配列が4から8に並べ替えられます。 たとえば、0から2までのサブ配列に対してこれを繰り返すと、次のようになります。

Sorting input: 3,2,1,4,7,8,9,5,5 from 0 to 2
Pivot: 1
Partition Index: 0

When j == 0 => input[0] == 3 => No Change
When j == 1 => input[1] == 2 => No Change

After Loop => Swap 1 for 3 => input := 1,2,3,4,7,8,9,5,5, partitionIndex := 0Copy

アルゴリズムが機能するように入力配列全体をまだ渡していることに注意してください。ただし、インデックスが低い場合と高い場合があるため、実際には気になるビットにのみ注意を払います。これは効率です。アレイ全体またはそのセクションを複製する必要はありません。

アルゴリズム全体で、配列全体を並べ替えて、12の異なるスワップを実行して結果を取得しました。

6.2. Hoareパーティショニング

Hoareパーティショニングは、Quicksortアルゴリズムが最初に公開されたときにTonyHoareによって提案されました。 アレイ全体を低から高に処理する代わりに、両端から中央に向かって一度に繰り返します。 これは、より多くの反復とより多くの比較がありますが、スワップが少ないことを意味します。

多くの場合、メモリ値を比較する方がスワップするよりも安価であるため、これは重要な場合があります。

擬似コードの場合：

fun quicksort(input : T[], low : int, high : int) 
    if (low < high) 
        p := partition(input, low, high) 
        quicksort(input, low, p) // Note that this is different than when using Lomuto
        quicksort(input, p + 1, high)

fun partition(input : T[], low: int, high: int) : int
    pivotPoint := floor((high + low) / 2)
    pivot := input[pivotPoint]
    high++
    low-- 
    loop while True
        low++
        loop while (input[low] < pivot)
            high--
        loop while (input[high] > pivot)
        if (low >= high)
            return high
        swap(input[low], input[high])
Copy

実例として、以前の配列を分割できます。

Sorting input: 3,7,8,5,2,1,9,5,4 from 0 to 8
Pivot: 2

Loop #1
    Iterate low => input[0] == 3 => Stop, low == 0
    Iterate high => input[8] == 4 => high := 7
    Iterate high => input[7] == 5 => high := 6
    Iterate high => input[6] == 9 => high := 5
    Iterate high => input[5] == 1 => Stop, high == 5
    Swap 1 for 3 => input := 1,7,8,5,2,3,9,5,4
    Low := 1
    High := 4
Loop #2
    Iterate low => input[1] == 7 => Stop, low == 1
    Iterate high => input[4] == 2 => Stop, high == 4
    Swap 2 for 7 => input := 1,2,8,5,7,3,9,5,4
    Low := 2
    High := 3
Loop #3
    Iterate low => input[2] == 8 => Stop, low == 2
    Iterate high => input[3] == 5 => high := 2
    Iterate high => input[2] == 8 => high := 1
    Iterate high => input[1] == 2 => Stop, high == 1
    Return 1Copy

一見すると、これはより多くの作業を行っているより複雑なアルゴリズムのように見えます。 ただし、全体的に安価な作業を行います。 同じ結果を達成するためにLomutoパーティショニングスキームで必要な12の代わりに、アルゴリズム全体で8つのスワップのみが必要です。

7. アルゴリズムの調整

正確な要件に応じて、通常のアルゴリズムに対して行うことができるいくつかの調整があります。 これらはすべてのケースに適合するわけではないため、適切な場合にのみ使用する必要がありますが、結果に大きな違いをもたらす可能性があります。

7.1. ピボットの選択

ピボットする要素の選択は、アルゴリズムの効率性にとって重要な場合があります。 上記では、固定要素を選択しました。 これは、リストが本当にランダムな順序でシャッフルされている場合はうまく機能しますが、リストの順序が高いほど、効率が低下します。

リスト1、2、3、4、5、6、7、8、9 を並べ替える場合、Hoareパーティショニングスキームはスワップなしでそれを行いますが、Lomutoスキームには44が必要です。  同様に、リスト 9、8、7、6、5、4、3、2、1 には、Hoareで4回、Lomutoで24回のスワップが必要です。

Hoareパーティショニングスキームでは、これはすでに非常に優れていますが、Lomutoスキームは大幅に改善できます。 ピボットの選択方法に変更を加えることで、3つの固定小数点の中央値を使用することで、劇的な改善を得ることができます。

この調整は、単に3の中央値として知られています。

mid := (low + high) / 2
if (input[mid] < input[low])
    swap(input[mid], input[low])
if (input[high] < input[low])
    swap(input[high], input[low])
if (input[mid] < input[high])
    swap(input[mid], input[high])Copy

これは、アルゴリズムのすべてのパスに適用されます。 これにより、3つの固定小数点が取得され、逆の順序で事前に並べ替えられます。

これは珍しいようですが、その影響はそれ自体を物語っています。 これを使用してリストを並べ替える1、2、3、4、5、6、7、8、9は16回のスワップを実行しますが、以前は44回でした。 これは、行われた作業の64% r教育です。 。 ただし、リスト 9、8、7、6、5、4、3、2、1 は、以前の24スワップではなく、19スワップにしかドロップせず、リスト 3、7 8、5、2、1、9、5、4 は、以前は12だった18まで上がります。

7.2. 繰り返される要素

直接等しい要素が多数ある場合、クイックソートはわずかに影響を受けます。 それでもこれらすべてをソートしようとし、必要以上に多くの作業を行う可能性があります。

私たちが行うことができる1つの調整は、これらの等しい要素を分割フェーズの一部として検出し、単一のポイントではなく、それらの両側の境界を返すことです。 次に、等しい要素のストレッチ全体をすでにソートされているものとして扱い、どちらかの側の要素を処理することができます。

これを擬似コードで見てみましょう。

fun quicksort(input : T[], low : int, high : int) 
    if (low < high) 
        (left, right) := partition(input, low, high) 
        quicksort(input, low, left - 1) 
        quicksort(input, right + 1, high)Copy

パーティショニングスキームがピボットを返すたびに、同じ値を持つすべての隣接する要素の下限と上限のインデックスが返されます。 これにより、リストを処理しなくても、リストのより大きなスワスをすばやく削除できます。

これを実装するには、要素が等しいか小さいかを比較できる必要があります。 ただし、これは通常、実装が簡単な比較です。

8. アルゴリズムのパフォーマンス

クイックソートアルゴリズムは一般的に非常に効率的であると考えられています。 平均して、任意の入力をソートするためのパフォーマンスがあります。

元のLomutoパーティショニングスキームは、リストがすでに並べ替えられており、最後の要素をピボットとして選択した場合に低下します。 これまで見てきたように、ピボット選択に中央値3を実装すると、これは改善されます。実際、これによりに戻ります。

逆に、Hoareパーティショニングスキームは、の代わりに繰り返し実行されるため、より多くの比較が可能になります。 これは、スワップが少なくなったとしても、再帰がより多くの比較を行うことを意味します。

9. 概要

ここでは、クイックソートとは何か、およびアルゴリズムがどのように機能するかについて紹介しました。 また、さまざまなケースでアルゴリズムに加えることができるいくつかのバリエーションについても説明しました。