sorting - クイックソートを使用して配列内のk番目に小さいアイテムを見つける=>予想される実行時間?

Question

修正版のクイックソートを使用して配列内の k 番目に小さい項目を検索している場合、予想実行時間が O(n) になるのはなぜですか?

私が使用しているアルゴリズムは次のことを行います。

1) Runs quick sort on the array
2) If k is > the correct location of pivot, then run quicksort on the 2nd half.
Otherwise run it on the first half.

これには O(n * logn) の作業が必要になるという印象を受けました。

Answer 1

それは、本で説明されているアルゴリズムではありません。（1）、（2）などで1つのパーティションを実行する可能性が高くなります。