Insertion Sorting

What is Insertion Sorting?

Insertion Sorting is another type of sorting algorithm where we try to iteratively build a sorted portion of the array, it is done by pushing all the sorted elements to the left subarray of the greater element keeping the greater element in an appropriate position.

Let us understand insertion sorting with a real-time example:

Say you have a playlist on Spotify which is unsorted and plays songs in a random order and it consist of the songs which you don’t like.

So what is the solution?

Here is the solution what you do is pick one of your favorite song such that it starts with some alphabet say a so now everything after a will be in a sorted order.

Now let us see the implementation of insertion sort in C:

#include<stdio.h>

void insertionSort(int arr[], int n){
int i,j,key;//initialization of the variables
for(i=1;i<n;i++){
key=arr[i];
j=i-1;
while(j>=0&&arr[j]>key){
    arr[j+1]=arr[j];

j=j-1;


}
arr[j+1]=key;
}
}


int main()
{
    int i,n;
    printf("Enter the size of array: ");
   scanf("%d",&n);
   
   int arr[n];
   
   printf("The elements in the array: ");
   
   for(i=0;i<n;i++){
       scanf("%d",&arr[i]);
       
   }
   insertionSort(arr,n);
   
   printf("Sorted array: ");
   
   for(i=0;i<n;i++){
       printf("%d ",arr[i]);
       
   }
    
}

//function explanation:

Now splitting the function insertionSort:

void insertionSort(int arr[], int n){

int i,j,key;//initialization of the variables
for(i=1;i<n;i++){
in this scenario we have started our iteration from the first position considering that the zero position index is already sorted and running it upto n. 
key=arr[i];
in this scenario we are initializing the key variable to arr[i] in order not to loose the original value of the current element because while swapping sometimes the original value might be lost.

j=i-1;
in this scenario we are initializing the value of j to i - 1 in order to iterate the elements in sorted portion from right to left, comparing it with the key element and performing necessary swap operation..

while(j>=0&&arr[j]>key){
    arr[j+1]=arr[j];
in this scenario we are going to check whether the value is greater than or equal to zero and comparing the value of j with the key so if the condition is true then the swap operation will take place.

j=j-1;
or this scenario will take place where we are going to decrement the value of j then increment and initialize it to the key.
}
arr[j+1]=key;
the value of j after decrementing will be added here and updated as the new key value.
}
}