7

私は現在、暇なときにアルゴリズムを学んでいますが、第3章のselect（）アルゴリズムを研究しているときに、次の質問があります。

Aからnまでの数の配列を使用している場合、select（）アルゴリズムを使用して中央値（n / 2番目に小さい数）を見つけることができることを理解しています。

1）しかし、これは私が理解するのに苦労しているビットです。A = [3、7、5、1、4、2、6、2]。それが配列だとします。Partition（）の各呼び出し後の配列の内容、およびSelect（）の各再帰呼び出しのパラメーターは何ですか。

誰かがこれをどのように解決しているか説明できますか？

以下は、2つのアルゴリズムの擬似コードです。

Select(A, p, r, k) {
    /* return k-th smallest number in A[p..r] */
    if (p==r) return A[p] /* base case */
    q := Partition(A,p,r)
    len := q – p + 1
    if (k == len) return A[q]
    else if (k<len) return Select(A,p,q-1,k)
    else return Select(A,q+1,r,k-len)
}

2番目のコードは

Partition(A, p, r) { /* partition A[p..r] */
    x := A[r] /* pivot */
    i := p-1
    for j := p to r-1 {
        if (A[j] <= x) {
            i++
            swap(A[i], A[j])
        }
    }
    swap(A[i+1], A[r])
    return i+1
}

私が使用している本は、AnneKaldewaijによるTheDerivationofAlgorithmsと呼ばれています。

4

1 に答える 1

10

このアルゴリズムは2つのステップで機能します。分割ステップは、いくつかのピボット要素を選択し、ピボットよりも小さいものはすべて一方の側に、ピボットよりも大きいものはすべて反対側にあり、ピボットが正しい位置にあるように配列の要素を再配置することによって機能します。たとえば、配列が与えられた場合

3  2  5  1  4

3のピボットを選択すると、次のように配列を分割できます。

2  1  3  5  4
+--+  ^  +--+
 ^    |    ^
 |    |    +--- Elements greater than 3
 |    +-------- 3, in the right place
 +------------- Elements less than 3

配列をソートしていないことに注意してください。ソートに近づきました。ちなみに、これはクイックソートの最初のステップです。

次に、アルゴリズムは次のロジックを使用します。インデックスkに属する要素をソートされた順序で検索するとします（k番目に小さい要素）。次に、選択したピボットに関連して、次の3つのオプションがあります。

  1. ピボットは位置kにあります。次に、ピボットが適切な場所にあるため、探している値はピボットである必要があります。終わったね。
  2. ピボットはkより大きい位置にあります。次に、k番目に小さい要素がピボットの前の配列の部分にある必要があるため、配列のその部分でk番目に小さい要素を再帰的に検索できます。
  3. ピボットはkよりも小さい位置にあります。次に、k番目に小さい要素は配列の上部領域のどこかにある必要があり、そこで再帰できます。

この場合、2番目に小さい要素（位置2の要素）が必要であると想定します。ピボットが位置3に到達したため、これは、2番目に小さい要素が配列の前半のどこかにある必要があることを意味します。したがって、サブ配列で再帰します。

2  1

実際の中央値要素が必要な場合は、ピボットが配列の中央でスマックになってしまったため、中央値が3であると出力するだけで完了します。

最後に、4番目に小さい要素のようなものが必要な場合、ピボットは位置4の前にあるため、配列の上半分、つまり配列の上半分で再帰します。

5  4

この領域の前に3つの要素があるため、ここで最初の最小要素を探します。

アルゴリズムの残りの部分は、パーティショニングステップ（おそらくアルゴリズムの最も複雑な部分）を実行する方法と、再帰するかどうか（少し難しい）についての3方向の選択を実行する方法の詳細です。ただし、この高レベルの構造がアルゴリズムの意味を理解するのに役立つことを願っています。

お役に立てれば！

于 2012-03-05T22:20:29.560 に答える