The program sorts an array based on given input. There are bunch of sorting techniques such as Bubble sort, Selection sort and more to achieve this functionality. In this, we’ll be discussion Insertion Sort technique.
In this sorting technique, the number that needs to be sorted is known as Key. This algorithm is efficient for sorting a small unit of elements.
It can be considered as a way that people use to sort playing cards. A set of cards facing towards the table are picked one by one and put at their correct place.
we compare a new card lifted from the table with the existing ones in our hand.
Similarly, in insertion sort at each iteration, an element from the input dataset is taken out and placed to the location where it belongs to be. It is followed until all the inputs get placed and sorted.
for j=1 to Array.Length key=arr[j] k=j-1; while k>=0 && arr[k]>key arr[k+1] = arr[k] arr[k]=key k= k-1 End While End for
#include<conio.h> #include<stdio.h> #define size 6 void main() { int arr[size],i,j,k,key,temp; printf("Please enter elements: \n "); for(i=0;i<=size-1;i++) { scanf("%d",&arr[i]); } for(j=1;j<=size-1;j++) { key=arr[j]; k=j-1; while (k>=0 && arr[k]>key) { arr[k+1] = arr[k]; arr[k]=key; k=k-1; } } printf(" \n Entered Elements :"); for(i=0;i<=size-1;i++) { printf("\n %d ",arr[i]); } getch(); }
Output:
It requires a constant amount O(1) of additional memory space and O(n2) comparisons in the worst case and average case to sort an array.
However, sorting time to sort the same size of elements can be varied depending on how much a given array is already sorted.
This post was last modified on September 29, 2020