The purpose of this problem is to evaluate the performance of randomized quick sort in a given instance. Randomized quick sort is an algorithm that takes as input an array of N distinct integers and sorts them in ascending order. We will only consider inputs where all elements to be sorted are different.
The randomized quick sort we will evaluate works as follows:
quick-sort(L)
if L has less than 2 elements
return L
otherwise:
let P be an element of L chosen at random with uniform distribution
let L0 be the list of all elements of L that are strictly less than P, in the same relative order as in L
let L1 be the list of all elements of L that are strictly greater than P, in the same relative order as in L
let L2 be quick-sort(L0)
let L3 be quick-sort(L1)
return the concatenation of L2, P and L3, in that order
We will define the cost of a call to quick-sort(L) as its individual cost, plus the cost of each of its recursive calls (if any). The individual cost of a call to quick-sort(L) is the number of elements less than P that are located to the right of P in L plus the number of elements greater than P that are located to the left of P in L.
You will be given a int[] L, which represents the input to be evaluated. Return the expected cost of quick-sort(L) when run over that list.
|