Insertion Sort

Insertion sort is a sorting algorithm in which the elements are transferred one at a time to the right position. In other words, an insertion sort helps in building the final sorted list, one item at a time, with the movement of higher-ranked elements. An insertion sort has the benefits of simplicity and low overhead.

In an insertion sort, 

the first element in the array is considered as sorted, even if it is an unsorted array. 

In an insertion sort, each element in the array is checked with the previous elements, resulting in a growing sorted output list. 

With each iteration, the sorting algorithm removes one element at a time and finds the appropriate location within the sorted array and inserts it there. The iteration continues until the whole list is sorted.

Advantages:

It is simple to implement and is quite efficient for small sets of data, especially if it is substantially sorted. It has low overhead and can sort the list as it receives data. 

It needs only a constant amount of memory space for the whole operation. 

It is more efficient than other similar algorithms such as bubble sort or selection sort.

Disadvantage:

However, an insertion sort is less efficient on larger data sets and less efficient than the heap sort or quick sort algorithms.

Kindly visit:

https://www.geeksforgeeks.org/insertion-sort/

An in-place algorithm is an algorithm that does not need an extra space and produces an output in the same memory that contains the data by transforming the input ‘in-place’. However, a small constant extra space used for variables is allowed.

Ex: Insertion sort

Merge-sort is an example of not-in-place sorting. Merge sort is not an in-place algorithm. It requires 0(n) memory space for the array data structure, and uses additional resources to copy elements between arrays, meaning it runs much slower for larger datasets.

/* C code to implement insertion sort  */

#include<stdio.h>

int main()

{

int n, i, a[50], j, temp;

printf(“Enter n”);

scanf(“%d”,&n);

printf(“\n Enter %d values to be sort ”,n);

for(i=0;i<n;i++)

{

scanf(“%d”,&a[i]);

}

/* insertion sorting */

for(i=1; i<n;i++)

{

j=i;

     while(j>0 && a[j-1]>a[j])

     {

     temp=a[j-1];

     a[j-1]=a[j];

     a[j]=temp;

     j=j-1;

     }

}

printf(“\n After Sort \n”);

for(i=0;i<n;i++)

{

printf(“\n %d”,a[i]);

}

return(0);

}