Insertion Sort

We consider we have two parts in array :

1) Sorted Part

2) Unsorted Part

In this algorithm we try to move element from unsorted part to sorted part. Basically we select element from unsorted part & place it in sorted part. We repeat this process until the array become sorted.

Note : We consider first element of array to be sorted

We consider j >= 0 because if by chance we reach at 0 this means we found out position & there is no more element left for comparison.

 

Algorithm :

ALGORITHM InsertionSort(A[], N)
BEGIN:
   FOR i = 2 TO N DO
       k = A[i]
       j = i - 1
       WHILE(A[j] > k AND j > 0) DO
         A[j+1] = A[j]
         j = j - 1
       A[j+1] = k
END;

 

Source Code : 

#include<bits/stdc++.h>
using namespace std;

void Sort(int a[], int sz)
{
  int k, i, j;	
  for(i = 1; i<sz; i++)
  {
    k = a[i];
    j = i-1;
    while(a[j]>k && j>=0)
    {
      a[j+1] = a[j];
      j -= 1;	
    }
    a[j+1] = k;
  }

  for(i = 0; i<sz; i++) cout << a[i] << " ";
}

int main()
{
  int a[] = {23, 3, 76, 43, 12, 11, 70};

  Sort(a, 7);

  return 0;
}