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:
In this post, we learned about insertion sort algorithm and its implementation program in C with and without function.
Challenge: Write C program to sort numbers in descending order using insertion sort in the comments.
For more programming articles and code snippets, visit programming articles.