Insertion sort in C

In this post, you’ll learn about the insertion sort algorithm in C and how to implement it in the C programming language with and without a function using example programs.

Insertion sort algorithm in C

Insertion sort algorithm is more efficient than bubble sort. From the word “insertion” we can easily interpret that it has something to do with insertion of elements.

The logic for insertion sort is that every element is picked up and inserted in the proper place. For example, if we have to arrange the numbers(elements) in ascending order then we pick one element and compare it with the previous element, if that is a larger element(number), we swap those two, and keep doing this until all the elements before that “picked element” are placed in proper place.

This is hard to understand without using the code. Therefore learn it from the code below.

Program: Insertion sort program in C

This is a C program to sort N numbers in ascending order using insertion sort, where N is the number of elements in the array and is entered by the user.

#include <stdio.h>
int main()
{
    int array[10];
    int i, j, num, temp;
    printf("Enter the number of elements: ");
    scanf("%d", &num);
    printf("Enter the elements of the array: ");
    for (i = 0; i < num; i++)
    {
        scanf("%d", &array[i]);
    }
    printf("\nInput array is:\n");
    for (i = 0; i < num; i++)
        printf("%d\t", array[i]);
    for(i=1;i<num;i++)
    {
        temp=array[i];
        j=i-1;
        while((j>=0)&&(array[j]>temp))
        {
            array[j+1]=array[j];
            j--;          
        }
        array[j+1]=temp;
    }
    printf("\n\nArray after insertion sort:\n");
    for (i = 0; i < num; i++)
        printf("%d\t", array[i]);
    printf("\n");
    return 0;
}

Output: Sort numbers in ascending order and print them

Enter the number of elements: 8
Enter the elements of the array: 37 92 20 17 111 49 58 65

Input array is:
37      92      20      17      111     49      58      65

Array after insertion sort:
17      20      37      49      58      65      92      111

We can separate the insertion sort algorithm to understand it properly using function. Below is a insertion sort example to implement the same.

Program: Insertion sort in C using function

This C program uses insertion sort algorithm inside a function to sort the numbers in descending order. The array elements(numbers) are entered by the user.

// Insertion sort program example in C using function
#include <stdio.h>
//function prototype
int bubblesort(int[], int);
int main()
{
    int array[10];
    int i, j, num;
    printf("Enter the size of array: ");
    scanf("%d", &num);
    printf("Enter the elements of the array: ");
    for (i = 0; i < num; i++)
    {
        scanf("%d", &array[i]);
    }
    printf("\nOriginal array is:\n");
    for (i = 0; i < num; i++)
        printf("%d\t", array[i]);
    printf("\n\nArray in decreasing order using insertion sort:\n");
    bubblesort(array,num);
    printf("\n");
    return 0;
}
//function definition
int bubblesort(int arr[], int size)
{
    int i, j, temp;
    for(i=1;i<size;i++)
    {
        temp=arr[i];
        j=i-1;
        while((j>=0)&&(arr[j]<temp))
        {
            arr[j+1]=arr[j];
            j--;          
        }
        arr[j+1]=temp;
    }

    for (i = 0; i < size; i++)
        printf("%d\t", arr[i]);
    
    return 0;
}

The output of the above C example program is:

Enter the size of array: 6
Enter the elements of the array: 92 654 34 453 8 565                                                                         

Original array is:
92      654     34      453     8       565

Array in decreasing order using insertion sort:
654     565     453     92      34      8

Also read: