Analysis of Permutation Problem

void indexsort( vector<int> & data)
{
   int i, n = data.size();

   for (i = 0; i < n; i++)
   {
      while(data[i]-1 != i)
         swap(data, i, data[i]-1);
   }
}

Here are the steps for potential function analysis:

• Define the ``operations'':

  For this problem, the operations are the execution of the swap call or the increment of the index i if no swap is needed.

• Define the potential function:

  $$\Phi(A,i) = (n-i)+\sum_{j=0}^{n-1} \chi(A[j] \neq j).$$

  Here, $\chi(e)$ is the indicator function: one if e is true, and zero otherwise.

  So, $\Phi(A,i)$ measures the distance of i from n plus the number of items still unsorted.

  Note that the potential function need not be computable quickly. It's mainly a mathematical definition.

• Define the amortized costs: $\hat{c}_t = 0$.
• Show that $c_t \le \hat{c}_t + \Phi(A_{t-1}, i_{t-1}) - \Phi(A_t, i_t)$:

  Here, A_t and i_t means the array and index after the tth operation.

  In this case, there are two operations: Swapping and incrementing i. We swap if A[i] is out of place. Then, c_t = 1, and

  

  If we increment i, then c_t = 1, and

  

• Now, the total work in the sequence of operations is bounded by the maximum initial value of the potential function.