Insertion sort

Why Insertion sort is called insertion sort?

Insertion sort is called "insertion sort" because it sorts a list by repeatedly taking the next unsorted element and inserting it into its correct position within the already sorted part of the list.

Working:

Sorting first element from unsorted array:

First we store first element of unsorted array into 'temp' which creates a empty space (hypothetically) and then we compare temp with the element in sorted array and if the temp is smaller than we right shift the element in the sorted array .In this case Temp is bigger than 3 so no swapping

Now 8 is inserted at index [1] in sorted array

Sorting array[2] from unsorted array:

Now temp is 1 and now we insert this 1 into its correct position in sorted array

Comparing it with the elements in sorted array and shifitng the elements to right if they are greater than temp.And we stop comparing when we reach to index 0

Inserting 1 to index arr[0] in sorted array

Sorting arr[3] from unsorted array:

Now temp is 4 and we will insert 4 in its correct position in the sorted array

Comparing it with the elements in sorted array and shifitng the elements to right if they are greater than temp.And we stop comparing when we reach to index 2 because 4>3 so no swapping

Inserting 4 to index arr[2] in sorted array

Sorting arr[4] from unsorted array:

Comparing it with the elements in sorted array and shiftng the elements to right if they are greater than temp.And we stop comparing when we reach to index 1 because 2>1 so no swapping

inserting 2 to index arr[1] in sorted array

Sorting arr[5] from unsorted array:

Comparing it with the elements in sorted array and shifting the elements to right if they are greater than temp.And we stop comparing when we reach to index 4 because 5>4 so no swapping

Sorted array

Implementation:

In insertion sort we compare one by one element from unsorted array with sorted array so we run a outer loop to select one by one elements from unsorted array ,and we start the iteration from index 1 cause we consider the index 0 to sorted hypothetically.And we store temp=arr[i] means we store selected element from unsorted array in temp

for (int  i = 1; i < n; i++)
    {
        temp=arr[i];
    }

now we compare the temp with the sorted array which is located at the left

and when we shift 8 to right and again we compare temp with 3

so here u can observe that we compare temp with the elements situated to its left side till the index 0

so our inner loop will be:

    for (int  i = 1; i < n; i++)
    {
        temp=arr[i];
        j=i-1;
        //inner loop
        while (j>=0&&arr[j]>temp)//this loop will run only if the temp is smaller 
        {
            arr[j+1]=arr[j];//shifting elements to right 
            j--;
        }

    }

at last when we reach to last index or the condition temp<(sorted array element) becomes false we insert the temp element

For eg:

here temp is 4 and further the condition temp<(sorted array element) becomes false

so we inserted the element

so the last step to insert element

    for (int  i = 1; i < n; i++)
    {
        temp=arr[i];
        j=i-1;
        //inner loop
        while (j>=0&&arr[j]>temp)//this loop will run only if the temp is smaller 
        {
            arr[j+1]=arr[j];//shifting elements to right 
            j--;
        }
        arr[j+1]=temp;//insertion of the element

    }

here u can observe that the element inserted at the position arr[j+1] why?

lets take an example to explain this

Here we inserted the temp(4) in the arr[j+1] and j=1 so arr[2]=temp

Full code

#include<iostream>
using namespace std;
int main(){
    int n;
    cout<<"enter the number of element"<<endl;
    cin>>n;
    int arr[n];
    int temp,j;

    for (int i = 0; i < n; i++)
        {
            cout<<"enter "<<i+1 <<"element"<<endl;
            cin>>arr[i];
        }

        cout<<"unsorted array"<<endl;

    for (int i = 0; i < n; i++)
        {
            cout<<arr[i]<<' ';
        }
        cout<<endl;
    for (int  i = 1; i < n; i++)
    {
        temp=arr[i];
        j=i-1;
        //inner loop
        while (j>=0&&arr[j]>temp)//this loop will run only if the temp is smaller 
        {
            arr[j+1]=arr[j];//shifting elements to right 
            j--;
        }
        arr[j+1]=temp;

    }


        cout<<"sorted array"<<endl;

    for (int i = 0; i < n; i++)
        {
            cout<<arr[i]<<' ';
        }
        cout<<endl;


    return 0;


}

For more detailed understand follow : https://www.youtube.com/watch?v=yCxV0kBpA6M&t=472s