Problem Statement
function quicksort(A) if (length(A) <= some constant S) then return slowsort(A) else k = random integer drawn uniformly from integers in [0, length(A) - 1] (left, pivot, right) = partition(A, k) return concatenate(quicksort(left), pivot, quicksort(right)) end if end function function partition(A, k) pivot = A[k] // We are assuming that the list contains no duplicates, so no other element is equal to the pivot left = elements in A that are smaller than pivot right = elements in A that are larger than pivot return (left, pivot, right) end function
Assume that partition(A) takes a * length(A) time units and slowsort(A) takes b * length(A)^2 time units. Further assume that the total running time is simply equal to the sum of the running times of all calls to partition() and slowsort(). As seen in the pseudo-code, quicksort does not call itself recursively on lists of length S or less, but instead calls slowsort().
Consider using the randomized quicksort algorithm to sort a list that is some permutation of elements {x | 1 <= x <= listSize}. Hence, the list is of length listSize, only contains integers between 1 and listSize, inclusive, and contains no duplicates. You are given the constants a, b and S, and asked to compute the expected total running time of randomized quicksort on a list of size listSize that obeys the constraints given above.
Definition
- Class:
- RandomizedQuickSort
- Method:
- getExpectedTime
- Parameters:
- int, int, int, int
- Returns:
- double
- Method signature:
- double getExpectedTime(int listSize, int S, int a, int b)
- (be sure your method is public)
Notes
- Your answer must be within 1E-9 absolute or relative error.
Constraints
- listSize will be between 1 and 1,000, inclusive.
- S will be between 1 and 10, inclusive.
- a and b will each be between 1 and 100, inclusive.
Examples
1
1
1
1
Returns: 1.0
Since listSize = S, quicksort will not call itself recursively, but will instead simply call slowsort. The call to slowsort will take 1 * (1^2) = 1 time units.
2
1
1
1
Returns: 3.0
Quicksort will randomly select one of the two elements to be the pivot and then recurse on lists of size 1 and 0. The recursive calls will take 1 * (1^2) = 1 and 1 * (0^2) = 0 time units respectively. In addition, the initial call to partition() will take 1 * 2 = 2 time units, so the total expected running time is 1 + 2 = 3.
3
1
1
1
Returns: 5.666666666666667
3
1
1
10
Returns: 17.666666666666668
10
5
3
2
Returns: 112.37380952380951
1000
10
100
100
Returns: 1544961.8218377363
1000
1
100
100
Returns: 1198591.266282178
1000
10
13
83
Returns: 609586.7035055718
1000
1
72
11
Returns: 842632.0450565031
1000
1
1
1
Returns: 11985.912662821782
410
10
11
70
Returns: 203194.56847447122
661
10
87
61
Returns: 740942.9800275661
67
6
67
80
Returns: 40173.4648502979
302
5
18
84
Returns: 110930.48458569139
180
7
100
56
Returns: 160367.61228241297
195
2
71
63
Returns: 122372.1598739174
340
9
41
56
Returns: 205242.37189523477
385
3
91
77
Returns: 361419.6691451162
161
1
64
42
Returns: 85301.47579140632
928
8
53
51
Returns: 695675.9299817674
772
10
5
4
Returns: 53148.21451465036
90
2
41
58
Returns: 28767.141838455627
860
2
96
20
Returns: 924084.7761291185
519
8
18
71
Returns: 247941.5277828018
962
1
2
29
Returns: 31579.88013730659
691
8
10
27
Returns: 148216.41138458758
59
10
68
20
Returns: 23333.54343548704
948
5
60
6
Returns: 606856.9776529927
193
9
11
43
Returns: 57052.656395326085
748
9
24
82
Returns: 483150.8713310129
630
4
4
10
Returns: 37402.85028067389
69
1
56
22
Returns: 25392.106846549155
177
8
82
65
Returns: 146905.65370797354
119
7
86
41
Returns: 79669.53668906933
932
8
91
94
Returns: 1227547.3171402165
438
6
9
31
Returns: 78374.86198646009
400
3
80
9
Returns: 299568.6223192181
278
4
40
62
Returns: 126004.07671602313
176
2
56
46
Returns: 84607.66290902313
826
2
47
99
Returns: 492902.1166012149
453
4
5
68
Returns: 82541.0518955589
155
2
8
4
Returns: 10005.162346715644
171
6
88
46
Returns: 128265.36871039502
516
1
98
97
Returns: 539642.7333896474
219
6
92
61
Returns: 190659.80635187472
188
7
53
57
Returns: 109693.50159325961
354
1
50
52
Returns: 176037.98082288858
442
9
7
10
Returns: 48149.56570468858
447
10
98
44
Returns: 466016.41089826386
267
7
39
3
Returns: 81137.3314650507
10
5
3
2
Returns: 112.37380952380951
1000
1
3
2
Returns: 35624.07132179874
3
3
3
3
Returns: 27.0
1000
1
100
100
Returns: 1198591.266282178
1000
1
1
1
Returns: 11985.912662821782
1000
1
1
10
Returns: 14988.912662821793
1000
1
99
98
Returns: 1186271.6869526901
100
5
3
2
Returns: 2326.755537594372
1000
1
77
99
Returns: 930255.9417039441
1000
2
3
3
Returns: 36458.23798846539
1000
10
10
99
Returns: 674182.0155171057
1000
5
3
2
Returns: 36782.37132179871
1000
1
20
20
Returns: 239718.25325643588
1000
10
100
100
Returns: 1544961.8218377363
1000
10
97
99
Returns: 1510291.300515936