Go 言語アルゴリズムの美しさ - 高度なソート

[[415242]]

この記事はWeChatの公開アカウント「roseduanの執筆場所」から転載したもので、著者はroseduanです。この記事を転載する場合は、roseduanが執筆しているローカルの公開アカウントまでご連絡ください。

この記事では、シェル ソート、ヒープ ソート、クイック ソート、マージ ソートなど、実際によく使用される複雑なソート アルゴリズムをいくつか見ていきます。

1. シェルソート

シェルソートは、実際には挿入ソートの最適化です。挿入ソートのプロセスは、データをソートされた区間とソートされていない区間に分割し、ソートされていない区間の値を順番に走査し、ソートされた区間の適切な位置に挿入することであることを思い出してください。

挿入ソートの最大の欠点の 1 つは、一度に 1 ビットしか移動できないことです。これは、極端な場合には非常に非効率的です。たとえば、データが 2 3 5 7 9 0 の場合、0 を要素の先頭に移動するには、配列全体を走査する必要があります。

これがシェルソートの最適化ポイントです。その中心的な考え方は、データ内の要素を複数のグループに分割し、各グループに対して個別に挿入ソートを実行することです。

簡単な例を見てみましょう。データは 35、33、42、10、14、19、27、44 です。まず、データは長さの 1/2 (つまり 4) のステップ サイズで 4 つのグループ、つまり {35,14}、{33,19}、{42,27}、および {10,44} に分割されます。

次に、各グループを個別に挿入して並べ替えると、並べ替えられた結果は次のようになります。

次に、ステップ サイズが半分の 2 に縮小され、配列が {14,27,35,42} と {19,10,33,44} の 2 つのグループに分割されます。

次に、これら 2 つのグループに対して個別に挿入ソートを実行すると、結果は 14 10 27 19 35 33 42 44 になります。

最後に、ステップ サイズを半分の 1 に減らし、配列をグループ (実際には配列自体) に分割し、挿入ソートを再度実行して、シェル ソート処理を完了します。

ご覧のとおり、Shell ソートは、データを可能な限りローカルに順序付けるために、配列を複数のグループに分割します。コードは次のとおりです。

 ShellSort関数(data[] int ) {
   長さ := len(データ)
   ステップ := 長さ / 2
ステップ>= 1 {
 i := 0; i < 長さステップ; i++ {
         j, k := i+ステップ、データ[i+ステップ]
 for ; j > step-1 && data[j-step] > k; j -= step {
            データ[j] = データ[jステップ]
         }
         データ[j] = k
      }
      ステップ /= 2
   }
 }

シェルソートの実用的な用途は多くなく、関連する複雑さは次のとおりです。

2. ヒープソート

ヒープソートを理解するには、まずバイナリヒープとは何かを理解する必要があります。バイナリ ヒープ (以下、ヒープと呼びます) は非常にエレガントなデータ構造です。これは特殊なバイナリ ツリーです。バイナリ ツリーの次の 2 つの特性を満たす場合、ヒープと呼ぶことができます。

• 完全な二分木である
• ヒープ内の任意のノードの値は、そのサブツリー内のすべてのノードの値以上（または以下）でなければなりません。

ノードがサブツリー内のノード値以上であるヒープは最大ヒープと呼ばれ、その逆も同様です。次に、ヒープの 2 つの例を示します。

定義と上の図からわかるように、ヒープの一つの特徴は、ヒープの最上位要素がヒープ内で最大の（または最小の）要素であるということです。

実際、ヒープは配列を使用して格納できます。ヒープの最上位要素は配列の最初の要素であり、インデックス i を持つ任意のノードの左の子は 2 * i + 1 で、右の子は 2 * i + 2 です。この対応により、配列内のヒープの格納は次のようになります。

ヒープとは何かがわかったので、早速本題に入り、ヒープに基づいたソートを実装する方法を見てみましょう。ヒープソートには通常、ヒープの構築とソートという 2 つのステップがあり、それぞれについて以下で説明します。

ヒープの構築

ヒープを構築するということは、順序付けされていない配列をヒープ（ここでは説明のために最大ヒープを使用します）に構築し、ヒープの特性に適合させることを意味します。たとえば、完全に順序付けされていない配列の場合、その元の状態とストレージ構造は次のようになります。

これを最大ヒープにするには、次のようにします。最初の非リーフ ノードから始めて、その子ノードの値と順番に比較します。子ノードの値より小さい場合は、ノードの順序を入れ替えて、リーフ ノードまで再度比較します。

このようにして、ヒープの特性は常に満たされ、任意のノードの値は常にそのサブツリー内のすべてのノードの値よりも大きくなります。

ソート

ヒープが構築されたら、次はそれをソートします。前述のように、ヒープには非常に重要な特徴があります。それは、ヒープの最上位要素が最大の要素であるということです。配列の長さをトラバースし、そのたびにヒープの最上位要素 (添え字が 0 の要素) を取り、それを配列の最後の要素と交換し、残りのデータをヒープに再編成し、ヒープの最上位の最大要素を取り続ける、という処理を繰り返します。

2 つのステップを組み合わせると、ヒープ ソートの完全な実装が得られます。コードは次のとおりです。

 // ヒープソート
関数HeapSort(data[] int ) {
   // ヒープを構築する
   長さ := len(データ)
 i := (長さ - 2) / 2; i >= 0; i -- {  
      ヒープ化(データ, 長さ, i)
   } 
 
   // 選別
長さ > 0の場合{
      長さ-  
      データ[長さ]、データ[0] = データ[0]、データ[長さ]
      ヒープ化(データ, 長さ, 0)
   }
 } 
 
 func heapify(data [] int , size , i int ) {
のために{
最大:= i
      2*i+1 <サイズ&& データ[2*i+1] > データ[最大]の場合 {
最大= 2*i + 1
      }
      2*i+2 <サイズ&& データ[2*i+2] > データ[最大]の場合 {
最大= 2*i + 2
      }
      i ==最大値の場合{
         壊す
      }
      データ[i]、データ[最大] = データ[最大]、データ[i]
      私 =最大 
   }
 }

関連する複雑さは次のとおりです。

マージソート

マージソートは分割統治の原則に基づいています。

分割統治法は、その名の通り、元の問題を複数の同一または類似のサブ問題に分解し、サブ問題を解決してサブ問題に対する解決策を統合することで、元の問題を解決できるようにする考え方です。

分割統治の考え方は、マージソート、クイックソート、バイナリサーチなど、多くの複雑なアルゴリズムの基礎となっています。

さて、本題に戻ってマージソートを見てみましょう。その概念は非常に簡単に理解できます。データセットをソートしたい場合、配列を 2 つのサブ配列に分割し、サブ配列をグループ化します。サブ配列をソートした後、結果をマージして元のデータのソート結果を得ることができます。

次の図は、問題を複数のサブ問題に分割するプロセスを示しています。

サブ問題が解決されたら、結果をマージする必要があります。マージのプロセスは次のとおりです。

コードは次のように実装されます。

 //マージソート
MergeSort関数(data[] int ) {
   mergeSortHelper(データ、0、長さ(データ)-1)
 } 
 
 mergeSortHelper関数(data [] int , lo, hi int ) {
   lo < hi {の場合
      中間 := 低 + (高-低)/2
      mergeSortHelper(データ、lo、mid)
      mergeSortHelper(データ、mid+1、hi)
      マージ(データ、低、中、高)
   }
 } 
 
 func merge(data [] int , lo, mid, hi int ) {
 temp := make([] int , hi-lo+1)
   i, j, k := lo, mid+1, 0
 i <= mid && j <= hi {の場合
      データ[i] < データ[j] {
温度[k] = データ[i]
         私は++
      }それ以外{
温度[k] = データ[j]
         j++
      }
      キロ++
   }
   コピー( temp [k:], data[i:mid+1])
   コピー( temp [k:], data[j:hi+1])
   コピー(データ[lo:hi+1]、 temp [:])
 }

関連する複雑さは次のとおりです。

3. クイックソート

クイック ソートは、通常「クイック ソート」と呼ばれます。これは、最も広く使用されているソート アルゴリズムです。プログラミング言語に組み込まれている多くのソート メソッドは、多かれ少なかれクイック ソートを使用しています。これは、クイック ソートの時間計算量が O(nlogn) に達する可能性があり、インプレース ソートであるためです。先に紹介したソート アルゴリズムでは、これら 2 つの利点を組み合わせることはできません。

クイックソートは、分割統治法を使用するという点でマージソートに似ていますが、その解決方法はマージソートとは多少異なります。

配列をソートする場合は、配列からデータをパーティション ポイント (ピボット) として選択し、パーティション ポイントより小さいデータをパーティション ポイントの左側に配置し、パーティション ポイントより大きいデータを右側に配置します。その後、配列が完全に順序付けされるまで、パーティション ポイントの両側のデータに対してこのパーティション分割方法を使用し続けます。

概念が少し抽象的かもしれないので、ソートプロセス全体を理解できるように、ここに図を描きました。

上図は、最初の分割のプロセスを示しています。ソートする配列の添え字が p ~ r であると仮定すると、配列の最後の要素 5 を分割点として、5 より小さい数字 0 3 1 2 は 5 の左側に移動し、5 より大きい数字 9 6 8 7 は 5 の右側に移動します。

次に、数字 5 を分割点として使用し、配列が完全に順序付けられるまで、その左側の数字 (添え字は p ~ q - 1) と右側の数字 (添え字は q + 1 ~ r) に対して同じ分割操作を実行します (以下を参照)。

次のアニメーションは、クイックソートの完全なプロセスを示しています (アニメーションでは最初の要素がパーティション ポイントとして選択されていることに注意してください)。

簡単な数式を使用してクイックソートを表現すると、次のように記述できます。

 int q = パーティション(データ、p、r);
 quick_sort(データ, p, r) = quick_sort(データ, p, q - 1) + quick_sort(データ, q + 1, r);

ここでは、パーティション ポイントを選択し、パーティション ポイントよりも小さいデータをその左側に、パーティション ポイントよりも大きいデータをその右側に配置し、パーティション ポイントの添え字を返すパーティション関数を示します。

実際、このパーティション関数はクイックソートの実装の鍵となります。では、この機能をどのように実装するのでしょうか。簡単に思いつく方法の 1 つは、元の配列を 1 回直接走査し、パーティション ポイントより小さいデータと大きいデータを順に取り出して、それぞれ一時配列に格納し、次に元の配列に順にコピーし直すことです。プロセスは次のとおりです。

これは単純ですが、欠陥があります。つまり、各パーティションが追加のストレージスペースを使用するため、クイックソートのスペース計算量は O(n) になり、インプレースソートにはなりません。

クイック ソートは、別の方法でパーティショニングを実装し、追加のストレージ スペースを使用しません。これはどのように行われるのでしょうか。理解を助けるために、図を描きました。

2 つのポインタ i と j が宣言され、配列の先頭から後方に移動します。ここでは 2 つの移動ルールがあります。

• まず、j が配置されている要素がパーティション ポイントより大きい場合、j は 1 つ前の位置に戻り、i は変更されません。
• 次に、j が配置されている要素がパーティション ポイントよりも小さい場合は、i と j が配置されている要素を交換し、同時に i と j を 1 つずつ戻します。

終了条件は、j が配列の末尾に移動し、パーティション ポイントと i が配置されている要素が交換されることです。ここで、i はパーティション ポイントの添え字です。

このプロセスを理解すると、クイックソートのコード実装を見るのは非常に簡単になります。次に例を示します。

クイックソート関数(データ[] int ) {
  クイックソートヘルパー(データ、0、長さ(データ)-1)
 } 
 
 func quickSortHelper(data [] int , lo, hi int ) {
  lo < hi {の場合
    mid := パーティション(データ、lo、hi)
    クイックソートヘルパー(データ、lo、mid-1)
    クイックソートヘルパー(データ、mid+1、hi)
  }
 } 
 
 func パーティション(データ[] int , lo, hi int ) int {
  ピボット、i、j := データ[hi]、lo、lo
 j < hi {の場合
    データ[j] < ピボット {
      データ[j]、データ[i] = データ[i]、データ[j]
      私は++
    }
    j++
  }
  データ[i]、データ[hi] = データ[hi]、データ[i]
戻る​
}

クイックソートの複雑さは次のとおりです。

この記事のすべてのコードは私の Github で閲覧できます: https://github.com/roseduan/Go-Algorithm