C Program for Sorting an Array using Insertion Sort

By | 14.09.2017

Sorting an Array using Insertion Sort


Write a C Program for Sorting an Array using Insertion Sort.  Here’s a simple C Program for Sorting an Array using Insertion Sort in C Programming Language.


Insertion Sort


Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

 

Algorithm
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

Time Complexity: O(n*n)

Auxiliary Space: O(1)

Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.


Also Read : : C Program for Sorting an Array using Bubble Sort

Below is the source code for C Program for Sorting an Array using Insertion Sort which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/* C Program for Sorting an Array using Insertion Sort */

#include<stdio.h>
#define MAX 100

int main()
{
        int arr[MAX],i,j,k,n;

        printf("\nEnter the number of elements : ");
        scanf("%d",&n);

        for(i=0; i<n; i++)
        {
                printf("\nEnter element %d : ",i+1);
                scanf("%d", &arr[i]);
        }

        /*Insertion sort*/
        for(i=1; i<n; i++)
        {
                k=arr[i]; /*k is to be inserted at proper place*/

                for(j=i-1; j>=0 && k<arr[j]; j--)
                        arr[j+1]=arr[j];
                arr[j+1]=k;
        }

        printf("\nSorted list is :\n");
        for(i=0; i<n; i++)
                printf("  %d  ", arr[i]);
        printf("\n");
        return 0;
}/*End of main()*/

OUTPUT : :


/* C Program for Sorting an Array using Insertion Sort */

Enter the number of elements : 7

Enter element 1 : 3

Enter element 2 : 1

Enter element 3 : 5

Enter element 4 : 7

Enter element 5 : 3

Enter element 6 : 0

Enter element 7 : 0

Sorted list is :
  0    0    1    3    3    5    7

Process returned 0

If you found any error or any queries related to the above program or any questions or reviews, you wanna ask from us, you may Contact Us through our contact Page or you can also comment below in the comment section. We will try our best to reach up to you in a short interval.


Thanks for reading the post…


Recommended Posts:

3 2 votes
Article Rating
Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments