Sorting an Array using Insertion Sort
Write a C Program for Sorting an Array using Insertion Sort. Here’s a simple C Program for Sorting an Array using Insertion Sort in C Programming Language.
Insertion Sort
Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
Algorithm
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]
Time Complexity: O(n*n)
Auxiliary Space: O(1)
Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
Also Read : : C Program for Sorting an Array using Bubble Sort
Below is the source code for C Program for Sorting an Array using Insertion Sort which is successfully compiled and run on Windows System to produce desired output as shown below :
SOURCE CODE : :
/* C Program for Sorting an Array using Insertion Sort */ #include<stdio.h> #define MAX 100 int main() { int arr[MAX],i,j,k,n; printf("\nEnter the number of elements : "); scanf("%d",&n); for(i=0; i<n; i++) { printf("\nEnter element %d : ",i+1); scanf("%d", &arr[i]); } /*Insertion sort*/ for(i=1; i<n; i++) { k=arr[i]; /*k is to be inserted at proper place*/ for(j=i-1; j>=0 && k<arr[j]; j--) arr[j+1]=arr[j]; arr[j+1]=k; } printf("\nSorted list is :\n"); for(i=0; i<n; i++) printf(" %d ", arr[i]); printf("\n"); return 0; }/*End of main()*/
OUTPUT : :
/* C Program for Sorting an Array using Insertion Sort */ Enter the number of elements : 7 Enter element 1 : 3 Enter element 2 : 1 Enter element 3 : 5 Enter element 4 : 7 Enter element 5 : 3 Enter element 6 : 0 Enter element 7 : 0 Sorted list is : 0 0 1 3 3 5 7 Process returned 0
If you found any error or any queries related to the above program or any questions or reviews, you wanna ask from us, you may Contact Us through our contact Page or you can also comment below in the comment section. We will try our best to reach up to you in a short interval.
Thanks for reading the post…
Recommended Posts:
- DFS Algorithm for Connected Graph
- BFS Algorithm for Connected Graph
- BFS Algorithm for Disconnected Graph
- Connected Components in an Undirected Graph
- Topological Sorting Algorithm Example