Chapter 7.1

   (13 19 9 5 12 8 7 4 21 2 6 11)
-> (() 13 19 9 5 12 8 7 4 21 2 6 (11))
-> (() (13) 19 9 5 12 8 7 4 21 2 6 (11))
-> (() (13 19) 9 5 12 8 7 4 21 2 6 (11))
-> ((9) (19 13) 5 12 8 7 4 21 2 6 (11))
-> ((9 5) (13 19) 12 8 7 4 21 2 6 (11))
-> ((9 5) (13 19 12) 8 7 4 21 2 6 (11))
-> ((9 5 8) (19 12 13) 7 4 21 2 6 (11))
-> ((9 5 8 7) (12 13 19) 4 21 2 6 (11))
-> ((9 5 8 7 4) (13 19 12) 21 2 6 (11))
-> ((9 5 8 7 4) (13 19 12 21) 2 6 (11))
-> ((9 5 8 7 4 2) (19 12 21 13) 6 (11))
-> ((9 5 8 7 4 2 6) (12 21 13 19) (11))
-> ((9 5 8 7 4 2 6) (11) (21 13 19 12))

The PARTITION returns r when all elements in the array A[p..r] have the same value.

PARTITION(A, p, r)
    x = A[r]
    i = p - 1
    c = 0
    for j = p to r - 1
        if A[j] == x
            c = c + 1
            exchange A[i + c] with A[j]
        else if A[j] < x
            i = i + 1
            exchange A[i] with A[j]
            if c > 0
                exchange A[i + c] with A[j]
    exchange A[i + c] with A[r]
    return i, i + c

QUICKSORT(A, p, r)
    if p < r
        q, s = PARTITION(A, p, r)
        QUICKSORT(A, p, q - 1)
        QUICKSORT(A, s + 1, r)

The looping statement has constant running time, and the count of the loop is \(n\), thus the running time of PARTITION is \(\Theta(n)\).

Modify PARTITION by changing the condition in the looping statement to \(A[j] \geq x\).