Type RANDOMIZED-PARTITION (CLRS 1-indexed)

Answer

RANDOMIZED-PARTITION(A, p, r) i = RANDOM(p, r) exchange A[r] with A[i] return PARTITION(A, p, r)

Swap a uniformly random element into the pivot slot A[r], then call ordinary PARTITION. The pivot is now random, so no fixed input can force the worst case.