Quicksort Pivot

int partition( vector<int> & A, int start, int end, int pivot_position )
{
  int x = A[pivot_position];
  int i = start - 1;
  int j = end + 1;
  
  while( true )
  {
    do j--;
    while( A[j] > x );
    
    do i++;
    while( A[i] < x );
    
    if( i < j )
      swap( A, i, j );    
    else
      return j;
  }
}

Define the ``operations'':
(1) Decrement j, (2) Increment i, (3) Swap.
Define the potential function:

$\begin{displaymath} \Phi(A, i, j) = 2j-2i+\chi(A[j] \le x)+\chi(A[i] \ge x).\end{displaymath}$
Define the amortized costs: $\hat{c}_t = 0$ .
Show that $c_t \le \hat{c}_t + \Phi(x_{t-1}) - \Phi(x_t)$ :
In all cases, c_t = 1.
(1) Decrement j:
$\begin{eqnarraystar} \lefteqn{\hat{c}_t + \Phi(A_{t-1}, i_{t-1}, j_{t-1}) - \Phi... ...t)}\ &\ge& 0 + 2 j_{t-1} - 2 (j_{t-1}-1) - 1\ &=& 1 = c_t.\end{eqnarraystar}$
(2) Increment i:
$\begin{eqnarraystar} \lefteqn{\hat{c}_t + \Phi(A_{t-1}, i_{t-1}, j_{t-1}) - \Phi... ...t)}\ &\ge& 0 - 2 i_{t-1} + 2 (i_{t-1}+1) - 1\ &=& 1 = c_t.\end{eqnarraystar}$
(3) Swap:
$\begin{eqnarraystar} \lefteqn{\hat{c}_t + \Phi(A_{t-1}, i_{t-1}, j_{t-1}) - \Phi... ...A_t[j_t] \le x)-\chi(A_t[i_t] \ge x)\ &=& 1+1-1-0 = 1 = c_t.\end{eqnarraystar}$
Note: This is assuming at most one value equal to the pivot.
Now, the total work in the sequence of operations is bounded by the maximum initial value of the potential function: $\Phi(A_0,i_0,j_0) \le 2n + 2$ .

Next: Web Walk Up: EXAMPLES Previous: While in Russia...