Quote:Original post by Bombshell_M Wikipedia's version is not optimal. Here's my implementation:
*** Source Snippet Removed ***
for n = 8, K = 2, PerfCount = 13 > n + log(n) - 2.
The problem with any algorithm of this nature is that its performance is dependent on the ordering of elements in the array. What's required to achieve the lower bound (if that's even possible) would be something more like a sorting network.
On the site you mentioned yourself, [a]http://en.wikipedia.org/wiki/Selection_algorithm[/a], there's a section with "Median of Medians" in the title. That's the algorithm I was talking about.
As for the algorithm you posted, I think you're a little confused about the problem you're trying to solve. Consider these two different problems: (1) Select the k-th smallest element (2) Select the k smallest elements Notice the plural in problem (2)?
Your algorithm solves problem (1). SaltyGoodness correctly points out that the runtime of your algorithm depends significantly on the ordering of the input array. Think about this: What will happen when A[PivotIndex] is the largest element? What will happen if after the first select_partition A[PivotIndex] is again the largest element among the remaining elements? You'll soon realize that your algorithm is very inefficient in the worst case (Omega(n^2), like quicksort).
But again, we weren't even talking about problem (1) yesterday. Problem (1) can be solved in linear time using the "Median of Medians" algorithm. Try groking that algorithm, as it uses a very interesting and clever technique. A simple search for "Median of Medians" on the internet will reveal more sources, though the best explanation I've seen so far is in Introduction to Algorithms by Cormen et al. Check it out in a library.
Now: The lower bound that you originally cited refers to the complexity of problem (2), and a similar technique can be used to obtain an efficient algorithm at least for k = 2.
