3

サイズnのソートされていない配列Aがあるとします。

線形時間で元のソートされていないリストからn/2、n / 2-1-1、n / 2 + 1番目に小さい要素を見つける方法は？

ウィキペディアで選択アルゴリズムを使用しようとしました（パーティションベースの一般的な選択アルゴリズムが実装しています）。

function partition(list, left, right, pivotIndex)
 pivotValue := list[pivotIndex]
 swap list[pivotIndex] and list[right]  // Move pivot to end
 storeIndex := left
 for i from left to right-1 
     if list[i] < pivotValue
         swap list[storeIndex] and list[i]
         increment storeIndex
 swap list[right] and list[storeIndex]  // Move pivot to its final place
 return storeIndex


function select(list, left, right, k)
 if left = right // If the list contains only one element
     return list[left]  // Return that element
 select pivotIndex between left and right //What value of  pivotIndex shud i select??????????
 pivotNewIndex := partition(list, left, right, pivotIndex)
 pivotDist := pivotNewIndex - left + 1 
 // The pivot is in its final sorted position, 
 // so pivotDist reflects its 1-based position if list were sorted
 if pivotDist = k 
     return list[pivotNewIndex]
 else if k < pivotDist 
     return select(list, left, pivotNewIndex - 1, k)
 else
     return select(list, pivotNewIndex + 1, right, k - pivotDist)

しかし、私は3つまたは4つのステップを理解していません。私は次の疑問を持っています：

  1. 私は正しいアルゴリズムを選択しましたか？それは私のプログラムに対して線形時間で実際に機能しますか？クイックソートに似ているので少し混乱しています。
  2. 関数の呼び出し中にメイン関数から選択すると、左、右、およびkの値がどうなりますか。私の配列がリスト[1...N]だと考えてください。
  3. select関数を3回呼び出す必要がありますか？1回はn / 2番目に小さいものを見つけるため、もう1回はn / 2 + 1番目に小さいものを見つけるため、もう1回はn /2-1番目に小さいものを見つけるためです。はいの場合、どのように電話しますか？
  4. また、関数select（3番目のステップ）「selectpivotIndex between left and right」で、プログラム/目的のためにピボットインデックスのどの値を選択する必要がありますか。

ありがとう！

4

1 に答える 1

2

クイックソートに似ていますが、クイックソートではピボットの左側と右側の両方を処理する必要があるのに対し、クイックセレクトでは片側のみを処理するため、線形です。

最初の呼び出しは、奇数のSelect(A, 0, N, (N-1)/2)場合です。N均等であれば、何をしたいのかを正確に決める必要がありますN。

中央値と左/右を見つけるには、中央値を見つけるためにそれを呼び出してから、配列のコンポーネントの最大値を左に、コンポーネントの最小値を右に実行することをお勧めします。中央値の選択フェーズが実行され、中央値の左側のすべての要素がそれより小さくなり、右側のすべての要素が大きくなります（または等しくなります）。これは、O（n）+ n / 2 + n / 2 = O（n）の合計時間です。

ピボットインデックスを選択する方法はたくさんあります。カジュアルな目的では、中間要素またはランダムインデックスのいずれかでおそらく十分です。

于 2012-04-13T03:52:26.100 に答える