パーティションを使用して、リスト内のK番目の最小の要素を見つける - 私はいくつかの異なる方法を使用して、リスト内のK番目の最小の要素を見つけるための割り当てを持っている私は

Question

オーケーの理解を助ける....

第一の方法は、リストをソートすることですK番目に小さい要素を返します。

「第2のアルゴリズムはにある：簡単に、私の考え方は

次の方法はクイックソートのパーティションを使用して、リスト= 10個の要素、昇順にソートリストは、その後、10番目の位置に要素を返すと言っていますこの手順では、Quicksortで使用されている「Partition」プロシージャを適用します。このプロシージャは、ピボットアイテムよりも小さいすべての要素が配列内に来るように配列を分割し、そのピボットアイテムより大きなすべての要素が後に来るようにします。ピボットアイテムがk番目のスロットに入るまで分割することでSelection Problemを解くことができます。これは、kがピボットポジションよりも小さい場合は左のサブアレイを再帰的に分割し、右のサブアkがピボットポジションより大きい場合はay。 K = pivotposition、我々が完了したら「

私は10項目のリストを持っていると言う：

3 8 9 2 4 1 7 10 6、5は旋回された状態で..私を知っています希望は、通常、2つの配列

3 2 4 1及び8 9 7 10 6

を持っていますが、私は理解していないことはあるでしょう：ピボット項目がであるまで、「我々は、パーティショニングによって選択問題を解決することができますk番目のスロット」。

k番目のスロットは何ですか？私はkth =配列の長さを考えていますので、この場合は10です。これは明らかに最低ではない6の値を持ちますが、正しいものではありません。

誰かがこのサンプル配列を使用できますが、このアルゴリズムの意味とkth/smallest要素の検索方法を教えてください。ありがとう

Answer 1

私はあなたが複雑な方法で解決策を見ていると思います。

これは、QuickSortを使用してk番目に小さい要素を見つける方法です（完全にクイックソートではありませんが、私はその理由を説明します）。

quicksortでは、ランダムピボット要素を選択し、配列全体を2つに分割し、左と右の部分配列を再帰的にソートしてソートされた配列全体を整形します。

この問題では、これを行う必要はありません。あなたがやっているすべては、ランダムなピボット要素を選択し、

1. です。
2. 配列を[Sub-array 1] Pivot [Sub-array2]で分割します。ここで、サブ配列1はピボットよりも小さい要素を持ち、サブ配列2はピボットよりも大きい要素 を持ちます。
3. サブアレイ1のサイズを確認してください。だからあなたの疑問に対処するための

If it is, 
     a.Greater than 'k' then your kth element lies in the first sub-array. Go recursively. Start sorting the sub-array1 alone and you can entirely discard the sub-array2 as you can be sure that 'kth' element cannot occur at a position greater than k! Repeat step-1 for the right sub-array 
     b.Lesser than 'k' then your kth element lies in the second sub-array. Again do as said above. Repeat step-1 for left subarray. 
     c.If the size of sub-array1 is k-1 then your pivot element must be the kth largest element in your array.Bingo! you have your 'kth' largest element in the array 

、

ここでは、それが全体の配列が、 の一部だけをソートされていません。（でも、それは完全に真実ではありません。あなたが取得します

Answer 2

クイックソートでは、ピボットポジションがkの場合は左がすべて小さく、右はすべてが大きいので、k番目の値が必要な場合はソートを続ける必要はありません。