|NU Year||Set: 2.(b) Marks: 5 Year: 2009|
Here, the analysis is slightly more tricky: Even fixing pivot, the number of swaps remains random.
More precisely: The indicesand run towards each other until they cross, which always happens at (by the correctness of Hoare's partitioning algorithm!). This effectively divides the array into two parts: A left part which is scanned by and a right part scanned by .
Now, a swap is done exactly for every pair of “misplaced” elements, i.e. a large element (larger than, 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 hypergeometricallydistributed: For the large elements we randomly draw their positions in the array and have positions in the left part. Accordingly, the expected number of pairs is given that the pivot is .
Finally, we average again over all pivot values to obtain the overall expected number of swaps for Hoare's partitioning: