Notes of Introduction to Algorithms (3rd Edition) --1

"In Place": Algorithm operates on the same inputs without using extra space, or use a constant number of extra space, which implies the inputs are the outputs after the algorithm is completed.

1: Insertion Sort (in place algorithm)
Inputs: an array of n elements: int inputs[n];
Outputs: an array of n elements inputs[n] following ascending order.

Idea: Suppose the first m (<n) elements have been sorted, the (m+1)th element is being sorted. Then insert (m+1)th element into an appropriate place in the first m elements. Therefore, after the insertion, the (m+1) elements are sorted as well.


int Insertion(int inputs[], int size)  
/*if array is passed as parameter, inputs should not have size with it: inputs[]; inputs[size] is not correct.*/
{
     for(int i=1;i<size;++i)
     {
          for(int j=0;j<i;++j)
          {
               if(inputs[i] < inputs[j])
               {
                  exchange(inputs[i],inputs[j]);
                  break;
               }
           }
      }
}

The internal loop can also be scanning from right to left:
          for(int j=i-1;j>-1;--j)
          {
               if(inputs[i] > inputs[j])
               {
                  exchange(inputs[i],inputs[j]);
                  break;
               }

           }

Complexity: O(n^2)