Data Structure and Algorithm

/************************************
-------------------------------
INSERTION SORT ALGORITHM
-------------------------------
Insertion.Sort(num,n,key)
1. for j from 2 to n
2. assign num[j] to key
   assign j - 1 to i
3. while i > 0 and num[i] > key
swap num[i+1] and num[i]
4. Return
*************************************/

#include "iostream.h"
#include "conio.h"

int main()
{
int num[50],N,i,j,key;
cout << "How many numbers? " ;
cin >> N;
cout << "\nEnter " << N << " Numbers\n";
for(int i = 0;i < N;i++)
  cin >> num[i];

for(j = 1;j < N;j++) //From Second Element to Last
{
  key = num[j]; //Assign num[j] to key
   i = j - 1;
   while(i >= 0 && num[i] > key)
    {
     //Swap two elements
   num[i + 1] = num[i];
      i--;
      num[i + 1] = key;
    }
}

//Print Output
cout << endl;
for(i = 0;i < N;i++)
  cout << num[i] << ' ';

getch();
return 0;
}

OUTPUT

How many numbers? 10

Enter 10 Numbers
25 65 47 88 64 10 -98 0 35 6

-98 0 6 10 25 35 47 64 65 88

Download Original File

Insertion.cpp