Explain Hoareās method of partitioning with suitable example.
Subject Algorithm Design 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(n1,nx,x1)Hyp(n−1,n−x,x−1) distributed: For the nxn−x large elements we randomly draw their positions in the array and have x1x−1 positions in the left part. Accordingly, the expected number of pairs is (nx)(x1)/(n1)(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:

1nx=1n(nx)(x1)n1=n613.