Insertion Sort C Program

  • by

Insertion Sort program in c language:
This is an example of c program to sort an array using Insertion Sort Algorithm. The elements of the array are entered by the user. Insertion sort c program is explained properly with algorithm (logic) and example.
C program for Insertion Sort is used to sort array in ascending order.You can also sort the array in descending order by modifying the condition in loop.

   Topics covered

  1. Insertion Sort Algorithm in c
  2. Insertion Sort c program
  3. Insertion Sort c program Explanation
  4. Insertion Sort c program using Function
  5. Insertion Sort Time Complexity in c

Insertion Sort Algorithm in c

This explains step-by-step the logic how Insertion Sort in c language works.

  1. Step 1:
    Insertion sort algorithm starts by comparing 2nd element of the array with the elements before it (only 1st element of the array in this case).
    If 2nd element is smaller than the 1st element then insert 2nd element at first position in the array.
    If 2nd element is larger than the remain 2nd second element in its position.
  2. Step 2:
    Now, 3rd element of the array is compared with the elements before it (1st element and 2nd element in this case).
    If 3rd element is smaller than 1st element then insert 3rd element at first position in the array.
    If 3rd element is larger than 1st element but smaller than 2nd element then insert 3rd element at second position in the array.
    If 3rd element is larger than both 1st and 2nd element then remain 3rd element in its position.
  3. Step 3:
    Similarly, 4th element of the array is compared with the elements before it (1st, 2nd element and 3rd elements in this case). And same procedure is repeated to insert the 4th element at its proper position in the array.
    After Step 3, starting 4 elements of the array will be sorted in Insertion Sort algorithm.

Insertion Sort c program


/* Insertion Sort in c */
#include <stdio.h> //printf() & scanf() Header File    
#include <conio.h> //clrscr() & getch() Header File 
int main()
{
    int a[20], n, i, j, item; 
    clrscr(); // to clear output screen
    /* To take number of elements in an array from user */
    printf("Enter how many elements should be in the array: "); 
    scanf("%d", &n); 
    /* Array Input */
    for (i=0; i<n; i++)
    {
        printf(Enter array element %d", i+1);  
        scanf("%d", &a[i]); 
    }
    /* Array Sort (In Ascending Order) */
    for (i=1; i<n; i++)
    {
	item = a[i];
  	/* Array Sort (In Ascending Order) */
        for (j=i-1; j>=0 && a[j]>item; j++) 
        {
            a[j+1] = a[j];
        }
	a[j+1] = item;
    }
    /* Print the sorted array */
    printf("Sorted Array - ");
    for (i=0; i<n; i++)
    {
        printf("%dt", a[i]);
    }
    getch(); //to hold output screen
    return(0); 
}

Output –

Enter how many elements should be in the array: 5
Enter array element 1: 40
Enter array element 2: 30
Enter array element 3: 10
Enter array element 4: 50
Enter array element 5: 20
Sorted Array - 10   20   30   40   50 

Insertion Sort C Program Explanation

Here, Insertion Sort in c is explained with a diagram. With pictorial explanation we can understand the program better.

sort array using insertion sort c program
sort array using insertion sort c program

Insertion Sort c program using Function

Here, all the code for Insertion Sort c program is written in a user-defined function void insertion_sort(int) and this function is called in main().


/* Insertion Sort c program */
#include <stdio.h> //printf() & scanf() Header File    
#include <conio.h> //clrscr() & getch() Header File 
/* function declaration */
void insertion_sort(int);
int main()
{
    int n;
    clrscr(); // to clear output screen
    /* To take number of elements in an array from user */
    printf("Enter how many elements should be in the array: "); 
    scanf("%d", &n); 
    /* calling function */
    insertion_sort(n);
    getch(); //to hold output screen
    return(0); 
}
void insertion_sort(int n);
{
    int a[20], n, i, j, item;
    /* Array Input */
    for (i=0; i<n; i++)
    {
        printf(Enter array element %d", i+1);  
        scanf("%d", &a[i]); 
    }
    /* Array Sort (In Ascending Order) */
    for (i=1; i<n; i++)
    {
	item = a[i];
  	/* Array Sort (In Ascending Order) */
        for (j=i-1; j>=1 && a[j]>item; j--) 
        {
            a[j+1] = a[j];
        }
	a[j+1] = item;
    }
    /* Print the sorted array */
    printf("Sorted Array - ");
    for (i=0; i<n; i++)
    {
        printf("%dt", a[i]);
    }
}

Output –

Enter how many elements should be in the array: 5
Enter array element 1: 40
Enter array element 2: 30
Enter array element 3: 10
Enter array element 4: 50
Enter array element 5: 20
Sorted Array - 10   20   30   40   50 

Insertion Sort Time Complexity in c

In Insertion Sort c program Time Complexity, we will explain the Worst case, Average case and Best case.

Best case Time Complexity:
O(n) is the Best Case complexity for Insertion Sort c program. Best case occurs when elements of the array are already sorted. So, there are no exchanges and the performance of Insertion Sort c program increases.

Worst case and Average case Time Complexity:
O(n*n) is the Worst Case complexity for Insertion Sort c program. Worst case occurs when elements of array are in reverse order. In this case there are maximum number of exchanges and the performance of Insertion Sort c program decreases.

There is only 1 comparison during Pass 1.
2 comparisons during Pass 2.
3 comparisons during Pass 3.
Worst case complexity will be O(n2).Note: This is c program for Insertion sort to sort numbers in an array. But this can be used in any language to sort elements of an array.

Best case complexity of insertion sort is O(n).
And average and worst case complexity is O(n2).Other c programs examples: