In this tutorial, we will learn and write a C program to implement insertion sort. Before that you may go through the following topics in C:
Insertion Sort Algorithm
Insertion sort is a simple sorting algorithm that sorts the elements in an array by comparing the values at index with all its prior elements. This process takes more time so it is only used for small data set.
This sorting takes the first index element and compares it to its largest value in an array and it moves the element to its right location.
C Program to implement Insertion sort
Question: Insertion sort program in C using function.
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 42 43 44 | // implementation of insertion sort in C program #include <stdio.h> void insertionSort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; //moving the value while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } int main() { int arr[30], n, i; printf("Enter the number of elements: "); scanf("%d", &n); printf("Enter %d Elements:\n", n); for (i = 0; i < n; i++) scanf("%d", &arr[i]); //calling sorting function insertionSort(arr, n); //Display the result printf("\nArray after sorting: \n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } |
Output:
Enter the number of elements: 6
Enter 6 Elements:
55
14
77
2
115
99
Array after sorting:
2 14 55 77 99 115
Time Complexity of Heap Sort:
- Best case:
0(n) - Average case:
0(n^2) - Worst case:
0(n^2)