- #1

- 36

- 0

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"

[tex]

\frac{(N-r-1)(r-1)}{N}

[/tex]

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:

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

Any CS grads out there who can help?