In this tutorial you will learn about the C Program to implement Insertion sort Algorithm and its application with practical example.
C Program to implement Insertion sort Algorithm
In this tutorial, we will learn to create a C program that will do insertion sort using C programming.
Prerequisites
Before starting with this tutorial we assume that you are best aware of the following C programming topics:
- Operators in C Programming.
- Basic Input and Output function in C Programming.
- Basic C programming.
- For loop in C Programming.
- Creating and Using the user-defined function in C programming.
What is Insertion Sort?
In every programming language, the sorting of data is a very important factor. In C Language. Many different techniques for sorting are available to work with but in this tutorial, we will focus on the Insertion Sort Technique.
In this technique, the work is done by inserting the smaller number to the first position. i.e.
the first and second number is sorted if the number is big then it is moved to the right and if it is small the moves to the left.
Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
The simple steps of insertion sort are as follows - Step 1 - Let us assume if the element already sorted. Return 1. Step 2 - Pick the next element store it separately in a key. Step 3 - Now, compare the key with all elements in the sorted array. Step 4 - If the element in the sorted array is smaller than the current element, then move to the next element. Else, shift greater elements in the array towards the right. Step 5 - Insert the value. Step 6 - Repeat until the array is sorted. |
Program For Insertion Sort
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <stdio.h> void insert(int x[], int n) /* function for sorting an array with insertion sort */ { int i, j, flag; for (i = 1; i < n; i++) { flag = x[i]; j = i - 1; while(j>=0 && flag <= x[j]) /* Move the elements greater than flag to one position next from their current position*/ { x[j+1] = x[j]; j = j-1; } x[j+1] = flag; } } void printArry(int x[], int n) /* function to print the array */ { int i; for (i = 0; i < n; i++) printf("%d ", x[i]); } int main() { int x[] = { 54, 65, 21, 32, 87, 98, 78, 89 }; int n = sizeof(x) / sizeof(x[0]); printf("Elements of array before sorting are - \n"); printArry(x, n); insert(x, n); printf("\nElements of array after sorting are - \n"); printArry(x, n); return 0; } |
Output:-
In the above program, we have first declared and initialized a set of variables required in the program.
- n = it will hold the size of the array.
- x[]= it will hold the elements in an array.
Function to print array:-
Insertion sort function
Main function body
