C++ Program to demonstrate Insertion Sort

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time.
How it works:

1. In insertion sort,elements are entered into the array(or list) 1-by-1.
2. When the first element is entered, it is placed at the 1st position in the list(0th position in an array).
3. When a new element is entered, it is compared to our already entered element and is decided whether to place before or after it in the list(array).
4. Now when the third element is entered is entered, it is compared with the greater element of the 2 already existing elements. If smaller, then it is swapped. If not, then the array can be considered sorted.
   If swapped, then is compared with the smaller element of the 2 already existing elements and swapped again with it if it is even smaller.
5. Similarly, all the the numbers to be placed in the list(array) are entered 1-by-1 and placed into the correct position right when they’re entered.

Example:

The following table shows the steps for sorting the sequence 5 7 0 3 4 2 6 1. On the left side the sorted part of the sequence is shown in red. For each iteration, the number of positions the inserted element has moved is shown in brackets. Altogether this amounts to 17 steps.

5	7	0	3	4	2	6	1		(0)
5	7	0	3	4	2	6	1		(0)
0	5	7	3	4	2	6	1		(2)
0	3	5	7	4	2	6	1		(2)
0	3	4	5	7	2	6	1		(2)
0	2	3	4	5	7	6	1		(4)
0	2	3	4	5	6	7	1		(1)
0	1	2	3	4	5	6	7		(6)

In our program, We have used:

1. double arr[8]: A double datatype array of size 8 to store and sort any 8 numbers. Modify it to increase or decrease the number of elements to be entered and sorted (Also modify the conditions in the for loops.)
2. int swaps: Integer variable to count the number of swaps performed.
3. 1st for loop: To traverse through the array 8 times, accept 8 numbers and place them in their appropriate place (With the help of a nested while loop).
4. int j=i: To start the array index for the while loop from i(location where the latest element has been placed).
5. Nested while loop: This loop is nested in the above for loop. It compares and swaps the elements until the newly-inputted element reaches its appropriate place.
6. swap(arg1,arg2): It is a predefined function and it swaps the data values of the 2 arguments passed to it.

The Program:
//Variables:
//double arr[8]: An array to store and sort 8 elements.
//int swaps: Integer variable to count the number of swaps performed.

#include<iostream>

int main()
{
 using namespace std;

 double arr[8]={0,0,0,0,0,0,0,0}; //Declare our array and initialize to 0
 int swaps=0; //Variable to count the number of swaps performed

 cout<<"Insertion sort Demonstration."<<endl<<endl;

 for (int i=0;i<8;i++) //To traverse through the array 8 times and accept 8 numbers
 {
  cout<<"Enter element number "<<i+1<<": "; //We use i+1 just to start the display of numbers from 1 rather than 0
  cin>>arr[i];

  int j = i;
  while(j>0 && arr[j]<arr[j-1]) //Runs until the new number has been placed in its correct place
  {
   swap(arr[j],arr[j-1]); //Swap if the elements are out of order.
   swaps++; //Increase swap counter
   j--; //decrease array index
  }
 }

 cout<<endl<<"Array After Sorting = ";
 for(int i=0;i<8;i++) //Loop to print our sorted array.
 {
  cout<<arr[i]<<" ";
 }
 cout<<endl;

 cout<<"Total number of swaps performed: "<<swaps<<endl<<endl;
 cout<<"Press any key to close this window...";

 cin.get();
 return 0;
}