Quicksort: Partitioning II

 Input: A[p..r]


Invariants: {All items  in $A[2..i]$ are $<$ the pivot.} 

{All items in $A[(i+1)..(unknown-1)]$ are $\geq$ the pivot}

$x = A[p];  i := p;$

for $unknown := p+1$ to $r$ do 

   if $A[unknown] < x$ then 

         $i := i+1$; swap$(A[i],A[unknown])$     swap$(A[1],A[i])$

$W(n)=n-1$ comparisons

15 7 23 5 20 3