Note: those marked with an asterisk I am not 100% confident in my answer/reasoning.

Please feel free to discuss the problems and my proposed solutions below!

5.1

Given the following array, that has gone through one round of partitioning during a quicksort procedure, which of the elements could be a pivot?

3 1 2 4 5 8 7 6 9

4, 5, or 9 could be the pivot.

5.2

Suppose array A has a length of l. If some α is strictly between 0 and 1/2, then the probability for a pivot, p, being chosen such that both subproblems are at least α*l can be proven by the following:

Consider three indices, p, p-α*l, and p+α*l where p is the index of the pivot. In order for the subproblems to have a length at least α*l then p-α*l must be >= 0 and p+α*l must be <= l. Hence p >= α*l and p <= l-α*l. This implies the size of the range of acceptable pivot selections is (l - α*l) - α*l = l - 2α*l = l(1 - 2α). The factor (1 - 2α) represents the fraction of the length of array A in which the pivot can be placed and satisfy the condition. Therefore, the probability of randomly selecting a pivot that satisfies the above condition is (1 - 2α).∎

Thus, C is the correct answer.

5.3

If every partition were to meet the conditions mentioned in the previous problem, then what would be the minimal and maximal successive recursive calls made before reaching the base case in either of the two upper level recursive calls?

To answer this, first consider if the pivot were chosen to perfectly divide the array into two equal parts at each recursion level. For this procedure, it was proven that the number of recursive calls is approximately log_2(n). The base 2 is because each part is 1/2 of the original n elements.

For the conditions mentioned in the previous problem, assume the pivot is chosen so that the left subarray just meets the length requirement. This would split the original array into an αn part and an αn + n(1 - 2α) = (1 - α)n part. Hence the two parts are α and (1 - α) fractions of the original n elements. In fact, they also represent the best and worst way to divide the original elements. So following the example of the log_2(n), then the best and worst case number of recursive calls will be and , respectively. Note that the bases both need to be risen to the -1 power as n is multiplied by them and not divided (similar to how 1/2^-1 = 2 for halving). Answer choice B matches these values.

5.4

For an array with sufficiently large number of elements, n, the best and worst case number of recursive calls made before hitting a base case will be Θ(logn) (if pivot is median every time) and Θ(n) (if pivot is smallest or largest value every time), respectively. Therefore B is the correct answer.

*5.5

In section 5.6 it was proven that all comparison-based sorting algorithms have a lower bound of Ω(nlogn) comparisons. We now want to extend this to apply to the expected running time of randomized comparison-based sorting algorithms.

I am unsure how to proceed for this proof, I would imagine I must prove that the expected number of comparisons made using randomized comparison-based sorting is at least nlogn. Unfortunately I am unsure how to prove that though and I need to move on to other things. Maybe I’ll return to this another day.

Programming Challenge

5.6

Implement quicksort:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class QuickSort {
    private static Random rand = new Random();
    
    public static void quickSort(int[] a, int l, int r){
        //base case
        if (l >= r)
            return;
        
        int i = choosePivot(l, r);
        
        swap(a, i, l);
        
        //partition returns index of new pivot, j
        int j = partition(a, l, r);
        
        
        quickSort(a, l, j-1);
        quickSort(a, j+1, r);
        
    }
    
    private static int choosePivot(int l, int r){
        return rand.nextInt(r-l+1)+l;
    }
    
    private static int partition(int[] a, int l, int r){
        int p = a[l];
        int i = l+1;
        
        for (int j = l + 1; j <= r; j++)
            if (a[j] < p)
                swap(a, i++, j);
        
        swap(a, l, i-1);
        
        return i-1;
    }
    
    private static void swap(int[] a, int i, int j){
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }
}