4 - Sorting Algorithm : Insertion Sort

Another sorting algorithm that we can use is insertion sort. We can use it for doing ascending or descending sorting :

1. If we need to do ascending sort, then we need to compare two elements : if we find an element whose value is greater than temp place its value to right.
2. If we need to do descending sort, then we need to compare two elements : if we find an element whose value is less than temp place its value to right.

First we have a program Insertion Sort - Ascending :
#include "iostream"
using namespace std;

int main (void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int k;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

for (i = 1; i < 8; i++)
{
temp = data[i];
j = i-1;
while ((j >= 0) && (data[j] > temp))
{
data[j+1] = data[j];
j = j-1;
}
data[j+1] = temp;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}
return 0;
}

Next we are presented with Insertion Sort - Descending :

#include "iostream"
using namespace std;

int main (void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int k;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

for (i = 1; i < 8; i++)
{
temp = data[i];
j = i-1;
while ((j >= 0) && (data[j] < temp))
{
data[j+1] = data[j];
j = j-1;
}
data[j+1] = temp;
}
cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}
return 0;
}

Next we will discuss Shell Sort