Expectation for # Exchanges (Quicksort Algorithm)

[rwinston]

Hi

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):

Consider the situation at the end of the partition process, when the bound
was the rth key value in order of magnitude. As a result of the final
exchange, the item which yielded this key value will occupy the rth position
of the segment, and the r- 1 items with lesser key value will occupy the
r- 1 positions below it in the store. The number of exchanges made in the
course of the partition process is equal to the number of items which
originally occupied the r- 1 positions of the lower resulting segment, but
which were removed because they were found to have key values greater
than the bound. The probability of any key value being greater than the
bound is (N- r- I)[N, and therefore the expected number of such items
among the r- 1 items which originally occupied what was to be the lower
resulting segment is"

<br /> \frac{(N-r-1)(r-1)}{N}<br />

Summing with respect to r, dividing by N, and adding one for the final
exchange of the item which yielded the bound, we get the absolute
expectation of the number of exchanges:

\frac{N}{6}+\frac{5}{6N}

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

Any CS grads out there who can help?

 

[LeonardoGuio]

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

Please, send me the Hoare original paper too.

Thanks.

 

[LeonardoGuio]

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).

The result will be the number you typed above.

Below, consider thar every sum is from r=1 to n:

(1/n)\sum(n-r-1)(r-1) = (1/n)\sum(nr-n-r^2+1)= (1/n)\sumnr - (1/n)\sumn - (1/n)\sum(r^2) + (1/n)\sum1 =(n+1)n/2 - n - (n+1)(2n+1)/6 + 1 = (n^2)/6 + (5/6) - n

Divide by n (probability) and sum 1 to the result (the exchange to put the pivot in the correct position) and we get:
n/6 + 5/6n

 

[rwinston]

Thanks Leonardo! That makes sense now :-)