QuickSort
SRM 486 · 2010-03-12 · by soul-net
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
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.
{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,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.
{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.
{50,40,30,20,10,15,25,35,45}
Returns: 11.07698412698413
{1,3,2}
Returns: 1.0
Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class QuickSort with a public method double getEval(vector<int> L) · 95 test cases · 2 s / 256 MB per case