Subject | Algorithm Design |
---|---|

NU Year | Set: 2.(b) Marks: 5 Year: 2009 |

Here, the analysis is slightly more tricky: Even fixing pivot xx, the number of swaps remains random.

More precisely: The indices ii and jj run towards each other until they cross, which always happens at xx (by the correctness of Hoare's partitioning algorithm!). This effectively divides the array into two parts: A left part which is scanned by ii and a right part scanned by jj.

Now, a swap is done exactly for every *pair* of “misplaced” elements, i.e. a large element (larger than xx, thus belonging in the right partition) which is currently located in the left part and a small element located in the right part. Note that this pair forming always works out, i.e. where the number of small elements initially in the right part equals the number of large elements in the left part.

One can show that the number of these pairs is hypergeometrically Hyp(n−1,n−x,x−1)Hyp(n−1,n−x,x−1) distributed: For the n−xn−x large elements we randomly draw their positions in the array and have x−1x−1 positions in the left part. Accordingly, the expected number of pairs is (n−x)(x−1)/(n−1)(n−x)(x−1)/(n−1) given that the pivot is xx.

Finally, we average again over all pivot values to obtain the overall expected number of swaps for Hoare's partitioning: