Function of pseudocode applying it at an array

Question

The following pseudocode is given:

partition(A,p,r){
  x<-A[r]
  i<-p-1
  for j<-p to r-1
       if A[j]<=x then
          i<-i+1
          swap(A[i],A[j])
  swap(A[i+1],A[r])
  return i+1

I have to describe the function of partition at the array: $A= \langle 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 \rangle$.

I found the following:

So the final form of the array is:

But how could I describe the function of partition at the array?

Answer 1

Perhaps it would help to formulate a loop invariant:

After each iteration of the loop, all elements with indices in $[p,i]$ are less than or equal to $x$, and those with indices in $(i,j]$ are larger than $x$. Those in $(j,r)$ have not been looked at yet.

Then body of the loop then just does what is necessary to maintain the loop invariant after $j$ has increased by one.

---

By the way, your "final form" looks like you haven't yet swapped the 12 in place between the two lists.