TopCoder problem "QuickSort" used in SRM 486 (Division I Level Two)



Problem Statement

    

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.

 

Definition

    
Class:QuickSort
Method:getEval
Parameters:int[]
Returns:double
Method signature:double getEval(int[] L)
(be sure your method is public)
    
 

Notes

-The returned value must have an absolute or relative error less than 1e-9.
 

Constraints

-L will contain between 1 and 50 elements, inclusive.
-Each element of L will be between 1 and 50, inclusive.
-All elements of L will be different.
 

Examples

0)
    
{1,2,3,4,5}
Returns: 0.0
With the elements in sorted order, the cost is 0 for any possible combination of pivot selections.
1)
    
{1,2,4,3,5,6}
Returns: 1.0
The 3 and the 4 need to be swapped. That can only happen when P=3 or P=4 are selected. All other selections for P add 0 cost, so the overall cost is always 1.
2)
    
{3,2,1}
Returns: 2.6666666666666665
If the first choice is P=1, the cost will be 2 for {2,3} being on its left plus 1 for recursively sorting the {3,2} list. If the first choice is P=3, an analogous situation also leads to an overall cost of 3. If the first choice is P=2, however, the cost is two because all other elements are in the wrong position, but after that, the recursive calls are free of charge because both lists have one element. Therefore, the expected cost is 2/3*3 + 1/3*2 = 2+2/3.
3)
    
{50,40,30,20,10,15,25,35,45}
Returns: 11.07698412698413

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10996

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14239&pm=10996

Writer:

soul-net

Testers:

PabloGilberto , battyone , ivan_metelsky

Problem categories:

Dynamic Programming, Math, Recursion