With a few friends we read the Algorithm Design Manual from Skiena. One of his (chapter 4) exercises asks for the number of comparisons that the quicksort algorithm does (comparing an element to the pivot) in case (a) the median is used as pivot or (b) the one-third element is used as pivot.
(a) pivot on median (the best one can do)
I got this far: the number of comparisons is $T(n)=n + 2T((n-1)/2)\approx n + 2 T(n/2) = \Theta(n\log n)$.
But I think it's also possible to come up with an exact number. Does anybody know how to do that?
(b) I was not able to solve the following: $T(n)=n + T((n-1)/3) + T(2(n-1)/3)$, as I do not know how to solve this with two different T's. And, also here I would also want to compute an exact number.
I wrote a small program to count the number of comparisons. It roughly looks like pivoting on the median, one-third, or one-tenth are only a constant factor apart, and pivoting on one-third is pretty close to $n\log_2{n}$.
If I'm allowed to paste links, here's my experimental result: http://postimg.org/image/fr18zahp3/full/
Any help would be greatly appreciated ;)
For the general case (pivoting on third, tenth or other constant fraction), consider the maximum depth quicksort will need to call itself recursively until it gets to an one-element array (which is sorted by definition). In each call, the size of its argument shrinks to at most constant multiple of the original size: $\frac{1}{2}$ in case of median, $\frac{2}{3}$ for the one-thirds approach or $\frac{9}{10}$ in the one-tenth case. Thus, the depth of the recursion is not going to exceed logarithm of the number of elements; the base of this logarithm is reciprocal of the shrinking factor. Obviously, every element of the array is going to be processed at most once at each "depth", so the upper bound on number of comparisons evaluates to $n\log_a n$ (where the base of logarithm is 2, 3, 10, ...).
Thanks to the nice property of logarithms, $\log_a n=(\log_a b)(\log_b n)$, all of these pivoting approaches are going to be within multiplicative factor of each other, belonging to $\Theta(n\log n)$. If you want to find the exact number of comparisons, you'll have to be very careful with your recurrence: expressions like $T(\frac{n-1}{2})$ don't make sense for even values of $n$.
I'll assume you want to solve the following recurrence in the "median" case: $$T(n)=n+T(\lfloor\frac{n-1}{2}\rfloor)+T(\lceil\frac{n-1}{2}\rceil)$$with initial condition $T(0)=0$. If that is the case, you can get further by considering how deep within the QuickSort recursion will each element be chosen as pivot and thus eliminated (it'll be compared with then-current pivots in all depths up to this one). Clearly, there is one pivot chosen in depth 1, two of them in depth 2, four in depth 4 and so on, all the way until all the sorted array is exhausted. The sum of their depths is then equal to the total number of comparisons. Unless I made a mistake, this results in $T(n)=nL-2^L+L+1$ when $2^{L-1}\leq n<2^L$ (Edit: The $+L$ term was missing originally).
Something similar can be done in the non-balanced cases too, although the calculation will most likely be even messier.