Quicksort Pivot Points
For quicksort, (in java, if it matters), is there a relationship between the number of pivot points (or pivot ind开发者_JS百科ices) and the size of a given array? For example, if the array size is 10, are there always going to be, say, 5 pivot points?
Yes, about n/2 is correct. However, I don't know why it would matter.
Not necessarily. It depends on the data and your algorithm. On average with decently random data and a decent implementation it should be on the order of log2(n) pivots.
You could have how ever many pivots you want (up to n I suppose...)
The more pivots you have, the more efficient the next recursion will be, although if it were too large (especially if it were non-constant) you would lose more time finding your pivot than you would gain.
I believe the typical is 3 potential pivots per iteration, but it's entirely dependent on implementation.
But remember that in the worst case, you're going to end up with n iterations (quicksort's worst case is O(n^2)
). That would naturally lend itself to requiring n pivots, and each iteration would do very little work.
Now, on the last iteration, you can expect about n/3 pivots. On the iteration above that, it would be n/6. On the next iteration it would be n/12. If you take the limit of that series, you end up with .6 repeating. So it looks like you can expect 2/3 n total pivots (because you'd have about 2/3 n total iterations)
精彩评论