I am reading Hoare's original paper where he derives the complexity of quicksort. I am trying to figure how he derives the expectation for the number of exchanges (sorry if this is a very CS-specific question):

[tex]
\frac{(N-r-1)(r-1)}{N}
[/tex]

[tex]\frac{N}{6}+\frac{5}{6N}[/tex]

I cant see how he derives the second equation, or what is involved in summing with respect to r.

I didn't understand the same as you. I was working in "suming in respect to r" and trying to figure out what does it mean. I've tryed to sum from r=1 to N, but it doesn't work. And I haven't understand why he uses (N-r-1) and do not use (N-r), what I think is correct.

Did you find the answer for your question? If yes, please put it here or send to me at leonardoguio@gmail.com

If you understand the number (n-r-1)/n as the propability of a given number to be bigger than the pivot and (r-1) the quantity of these given number that are in the wrong place, it's easy.

Sum in respect to r means that the number above consider that the pivot is in a given position r. But what position is this? The probability of the pivot to be the first number (and r=1) is 1/n, which is the same as the probability to the pivot be in any other position. So, in the middle case, we have to sum (n-r-1).(r-1)/n from 1 to n, which are the possible correct positions of the pivot, and then divide by n, because its a probability. After this, we have to sum 1 to the result, because it is the change of the pivot (to put the pivot in the correct position).