Partitioning subroutine PARTITION(A, P, DAlp. q x<alp p pivot A[p] Running time <p O(n) for n forj<p+ l to g elements do if Alji≤x then iti+1 exchange A[分>A exchange Alp<> Ai return i variant:x≤x Day 6 Introduction to AlgorithmsDay 6 Introduction to Algorithms L4.4 xx Running time = O(n) for n elements. Running time = O(n) for n elements. Partitioning subroutine PARTITION(A, p, q) ⊳ A[p . . q] x ← A[p] ⊳ pivot = A[p] i ← p for j ← p + 1 to q do if A[j] ≤ x then i ← i + 1 exchange A[i] ↔ A[j] exchange A[p] ↔ A[i] return i ≤≤xx ≥≥xx ?? pi q j Invariant: