0

クイック セレクト アルゴリズムの理解に問題があります。私はそれがクイックソートアルゴリズム（私がよく知っている）に基づいていることを知っており、おそらく配列の一部をソートせずに残して必要な結果が得られることを知っています。問題は、次の配列から 2 番目に小さい要素を見つけることです。

int a[4] = {1,3,5,2} ;

ここで、ピボットをランダムに選択するとします。この投稿によると、次の条件があります。

  • k == pivot. 次に、すでに k 番目に小さいことがわかりました。これは、パーティションの動作方法が原因です。k 番目の要素よりも小さい要素がちょうど k - 1 個あります。

  • k < pivot. 次に、k 番目に小さいものがピボットの左側にあります。

  • k > pivot. 次に、k 番目に小さいものがピボットの右側にあります。そして、それを見つけるには、実際に右側の k-pivot 最小数を見つける必要があります。

k==pivot k番目（私の場合は2番目に小さい要素）を見つけたことを誰かがどのように意味するかを説明できれば幸いです。またk < pivot、ピボットの左側に対してプロセスを繰り返す場合は?

4

2 に答える 2

1

はい、ピボットの左側にピボットよりも小さいpivok == k要素がある場合、配列の最小数、つまりピボットを見つけましたが、ピボット> k番目の最小要素であるため、配列の左側で検索します。 pivot <配列の k 番目に小さい要素なので、右側を検索して pivot を増やします。ウィキペディア から： k-1k-thk < pivot

// Returns the n-th smallest element of list within left..right inclusive (i.e. n is zero-based).
  function select(list, left, right, n)
     if left = right        // If the list contains only one element
         return list[left]  // Return that element
     pivotIndex  := ...     // select a pivotIndex between left and right, e.g. left + Math.floor(Math.random() * (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     // The pivot is in its final sorted position
     if n = pivotIndex
         return list[n]
     else if n < pivotIndex
         return select(list, left, pivotIndex - 1, n)
     else
         return select(list, pivotIndex + 1, right, n)

お役に立てれば ！

于 2014-03-16T07:13:11.617 に答える