Exercise 7.1.2

What value of $q$ does PARTITION return when all elements in the array $A[p \ldots r]$ have the same value? Modify PARTITION so that $q = \lfloor (p+r)/2 \rfloor$ when all elements in the array $A[p \ldots r]$ have the same value.

It returns $r$.

We can modify PARTITION by counting the number of comparisons in which $A[j] = A[r]$ and then subtracting half that number from the pivot index.

Python code

def partition(numbers, start = 0, end = None):
    last = end - 1 if end else len(numbers) - 1

    pivot_value = numbers[last]
    pivot       = start
    repetitions = 0

    for i in range(start, last):
        value = numbers[i]

        if value == pivot_value:
            repetitions += 1

        if value <= pivot_value:
            numbers[pivot], numbers[i] = numbers[i], numbers[pivot]
            pivot += 1

    numbers[pivot], numbers[last] = numbers[last], numbers[pivot]
    return pivot - repetitions // 2

def quicksort(numbers, start = 0, end = None):
    end = end if end else len(numbers)

    if start < end - 1:
        pivot = partition(numbers, start, end)
        quicksort(numbers, start, pivot)
        quicksort(numbers, pivot + 1, end)