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 log₂(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)