Insertion Sort In Detail

This technique actually goes through N-1 passes through the list where N is number of elements in the array. Each pass P can be considered to be for the elements from 1 to N-1. Each pass is actually an effort to place the element P in its correct position among the elements from position 0 to P.

Example:
Let us take an array of numbers A= (34, 8 , 64, 51, 32, 21).

Code:

  +---------------+-------+-------+-------+-------+-------+------+-----------------+
  |  Original     |   34  |   8   |   64  |   51  |   32  |  21  | Position Moved  |
  +---------------+-------+-------+-------+-------+-------+------+-----------------+
  | After P1      |    8  |   34  |   64  |   51  |   32  |  21  |           1     |
  +---------------+-------+-------+-------+-------+-------+------+-----------------+
  | After p2      |    8  |   34  |   64  |   51  |   32  |  21  |           0     |
  +---------------+-------+-------+-------+-------+-------+------+-----------------+
  | After p3      |    8  |   34  |   51  |   64  |   32  |  21  |           1     |
  +---------------+-------+-------+-------+-------+-------+------+-----------------+
  | After p4      |    8  |   32  |   34  |   51  |   64  |  21  |           3     |
  +---------------+-------+-------+-------+-------+-------+------+-----------------+
  | After p5      |    8  |   21  |   32  |   34  |   51  |  64  |           4     |
  +---------------+-------+-------+-------+-------+-------+------+-----------------+

Pseudo code: or Algorithm

Code:

  insertionSort(array A)
  begin
      for i := 1 to length[A]-1 do
      begin
          value := A[i];
          j := i - 1;
          done := false;
          repeat
              if A[j] > value then
              begin
                  A[j + 1] := A[j];
                  j := j - 1;
                  if j < 0 then
                      done := true;
              end
              else
                  done := true;
          until done;
          A[j + 1] := value;
      end;
  end;

Code in C language:

Code:

  void InsertionSort (int A[], int N)
  {
              int j, P;
              int Tmp;
   
              for (P=1; P<N; P++)
              {
                          Tmp=A[P];
                          for (j=P; j>0 && A[j-1]>Tmp; j--)
                          A[j] =A[j-1];
                          A[j]=Tmp;
              }
  }

Runtime Complexity:

It is O (N2). This is because there are two for loops and in the worst case the two for loops are both going to run N times. The point where Insertion Sort scores over Bubble Sort is its best case analysis. Note that when the elements are fully sorted, then the inner for loop will immediately break. This will give a runtime of O(N).



- Gaurav Singhal