Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Expectation for # Exchanges (Quicksort Algorithm)

  1. Mar 20, 2008 #1

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



    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?
  2. jcsd
  3. May 17, 2008 #2
    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

    Please, send me the Hoare original paper too.

  4. May 17, 2008 #3
    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)[tex]\sum[/tex](n-r-1)(r-1) = (1/n)[tex]\sum[/tex](nr-n-r^2+1)= (1/n)[tex]\sum[/tex]nr - (1/n)[tex]\sum[/tex]n - (1/n)[tex]\sum[/tex](r^2) + (1/n)[tex]\sum[/tex]1 =(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

  5. Jun 10, 2008 #4
    Thanks Leonardo! That makes sense now :-)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook