algorithm-quicksort
QuickSortアルゴリズムの概要
1. 前書き
この記事では、クイックソートアルゴリズムを見て、その仕組みを理解します。
クイックソートは、分割統治アルゴリズムです。 つまり、*各反復は、入力を2つの部分に分割し、それらを並べ替えてから、それらを結合して戻すことを意味します。
もともとはトニー・ホアによって開発され、1961年に公開されたもので、現在でも利用可能な最も効率的な汎用ソートアルゴリズムの1つです。
2. アルゴリズム要件
*クイックソートアルゴリズムを使用するための唯一の実際の要件は、2つの要素を比較するための明確に定義された操作*です。これにより、ある要素が厳密に別の要素よりも小さいかどうかを判断できます。 この比較の正確な性質は、一貫している限り重要ではありません。 直接等価比較は必須ではなく、より小さい比較のみが必要であることに注意してください。
*多くのタイプでは、これは否定できない比較*です。 たとえば、数字はこれを行う方法を暗黙的に定義します。 他のタイプはそれほど明確ではありませんが、ソートの要件に基づいてこれを定義できます。 たとえば、文字列を並べ替えるとき、大文字と小文字の区別が重要かどうか、またはUnicode文字がどのように機能するかを決定する必要があります。
3. バイナリツリーソート
*バイナリツリーソートは、ソートする要素で構成されるバランスの取れたバイナリツリーを構築するアルゴリズムです*。 これができたら、このツリーから結果を作成できます。
アイデアは、_pivot_をツリー上のノードとして選択し、ピボット要素よりも小さいかどうかに基づいて、すべての要素をノードの_left_または_right_ブランチに割り当てることです。 その後、ツリーを完全にソートするまで、これらのブランチを再帰的にソートできます。
* 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 4これにより、元の入力から2つのパーティションが得られました。 * _Left_リスト内のすべては厳密に_Pivot_より小さく、他のすべては_Right_リスト内にあります*。
次に、同じアルゴリズムを使用してこれら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 9*最初のパスから左のパーティションをソートすると、長さ1以下の2つのリストになりました*。 これらは既にソートされています-ソートされていないサイズ1のリストを持つことは不可能だからです。 これは、ここで停止し、代わりに適切なパーティションの残りの部分に集中できることを意味します。
この時点で、次の構造があります。
/ [1]
2
/ \ []
3
\ / [5 5 4]
7
\ [8 9]この時点で、すでにソートされたリストに近づいています。 ソートするパーティションがさらに2つあり、これで完了です。
1
/
2 4
/ /
3 5
\ / \
7 5
\
8
\
9*これにより、アルゴリズムの5つのパスでリストがソートされ、ますます小さなサブリストに適用されます*。 ただし、メモリのニーズは比較的高く、元のリストの9つの要素を並べ替えるために追加の17要素のメモリを割り当てる必要がありました。
4. クイックソートアルゴリズム
クイックソートアルゴリズムの概念は、バイナリツリーソートに似ています。 ソートする必要がある各ステップでサブリストを作成するのではなく、元のリスト内のすべての場所で実行します。
*選択したピボットの周りのリスト内の要素を動的に交換し、サブピボットをこのピボットのいずれかの側に再帰的にソートすることで機能します*。 これにより、スペース効率が大幅に向上します。これは、巨大なリストにとって重要になる可能性があります。
クイックソートは、_pivot_の選択と要素の分割のメカニズムという2つの重要な要因に依存しています。
*このアルゴリズムの鍵は_partition_関数です。これについてはすぐに説明します* これは、このインデックスの下のすべての要素がこのインデックスの要素よりも小さくソートされ、このインデックスの要素がその上のすべての要素よりも小さくソートされるように、入力配列にインデックスを返します。
これを行うには、配列内の要素の一部を交換して、このインデックスの適切な側になるようにします。
このパーティション分割が完了したら、このインデックスの両側の2つのパーティションにアルゴリズムを適用します。 最終的には、各要素が1つだけ含まれるパーティションがある場合に終了し、その時点で入力配列がソートされます。
* 4.1。 Lomuto Partitioning *
Lomuto Partitioningは、Nico Lomutoによるものです。 *これは、入力配列を繰り返し処理し、事前に選択されたピボット要素よりも厳密に小さい要素を交換して、配列の前にあるがスライドするターゲットインデックスに表示されるようにします*。
このスライディングターゲットインデックスは、新しいパーティションインデックスであり、次のより大きなアルゴリズムの再帰で使用するために返されます。
これの目的は、スライドターゲットインデックスが、配列内のそれより前のすべての要素がこの要素よりも小さく、この要素が配列内のそれ以降のすべての要素よりも小さくなるような位置にあることを保証することです。
これを擬似コードで見てみましょう。
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実際の例として、先ほどの配列をパーティション分割できます。
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 := 3この作業から、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 := 0アルゴリズムが機能するために、入力配列全体をまだ渡していることに注意してください。ただし、インデックスが低く、高いため、重要なビットにしか注意を払っていません。 *これは効率的で、アレイ全体またはそのセクションを複製する必要がありません。*
アルゴリズム全体で、配列全体をソートして、結果を得るために12の異なるスワップを実行しました。
* 4.2。 Hoare Partitioning *
Hoareパーティショニングは、クイックソートアルゴリズムが最初に公開されたときにTony Hoareによって提案されました。 アレイ全体を低から高に処理する代わりに、*両端から一度に中央に向かって反復します*。 これは、より多くの反復と比較がありますが、スワップは少ないことを意味します。
*多くの場合、メモリ値を比較する方がスワップするよりも安価なので、これは重要です。*
疑似コードの場合：
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 := low + (high - low) / 2
pivot := input[pivotPoint]
loop
loop while (input[low] < pivot)
low := low + 1
loop while (pivot < input[high])
high := high - 1
if (low >= high)
return high
swap(input[low], input[high])
low := low + 1
high := high - 1実際の例として、先ほどの配列をパーティション分割できます。
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 1一見すると、これはより多くの作業を行っている、より複雑なアルゴリズムのように見えます。 ただし、全体的には安価な作業を行います。 *アルゴリズム全体で必要なのは、同じ結果を得るためにLomutoパーティションスキームで必要な12個ではなく、8個のスワップだけです*。
5. アルゴリズムの調整
正確な要件に応じて、通常のアルゴリズムに対して行うことができる調整がいくつかあります。 これらはすべての場合に適合するわけではないため、適切な場合にのみ使用する必要がありますが、結果に大きな違いをもたらす可能性があります。
* 5.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])これをアルゴリズムのすべてのパスに適用します。 これにより、3つの固定点が取得され、逆の順序で事前にソートされます。
これは異常なように見えますが、その影響はそれ自体を物語っています。 *これを使用してリストを並べ替える_1、2、3、4、5、6、7、8、9_は、以前は44だったのに、16のスワップが必要になりました。 これにより、完了した作業が64％削減されます*。 ただし、リスト_9、8、7、6、5、4、3、2、1_は、これまでの24回ではなく、19回のスワップにのみ低下し、リスト_3、7、8、5、2、1、9 、5、4_は18になり、以前は12でした。
* 5.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)ここでは、パーティションスキームがピボットを返すたびに、同じ値を持つすべての隣接要素の下限インデックスと上限インデックスを返します。 これにより、リストの大きなスワスを処理することなくすばやく削除できます。
これを実装するには、要素が等しいかどうかを比較する必要があります。 ただし、これは通常、実装が簡単な比較です。
6. アルゴリズムのパフォーマンス
クイックソートアルゴリズムは一般的に非常に効率的であると考えられています。 *平均して、任意の入力をソートするための_O（n log（n））_パフォーマンスがあります*。
元のLomutoパーティションスキームは、リストが既に並べ替えられており、最終要素をピボットとして選択する場合、_O（n²）_に低下します。 これまで見てきたように、ピボット選択に中央値3を実装すると、これは改善され、実際、_O（n log（n））._に戻ります。
逆に、Hoareパーティションスキームは、_low-> p-1_ではなく、_low-> p_で再帰するため、より多くの比較を行うことができます。 これは、スワップが少なくなるとしても、再帰はより多くの比較を行うことを意味します。
7. 概要
ここでは、クイックソートとは何か、アルゴリズムの仕組みを紹介しました。 また、さまざまなケースでアルゴリズムに加えることができるいくつかのバリエーションも取り上げました。
