WAP for Insertion Sort in C. Insertion sort is a simple and efficient algorithm widely used for sorting a small list of elements. In this article, we will explore about insertion sort algorithm and its implementation in C language.
Table of Contents
Insertion Sort Algorithm
Insertion sort works similar to the way we might sort playing cards in our hands. The algorithm builds the sorted array one item at a time. It takes one element from the list and places it in the correct position within the sorted part of the list, Adjusting other elements accordingly.
Algorithm Steps
The Insertion sort algorithm can be broken down into the following steps-
- Start with the second element: Assume that the first element is already sorted. start with the second element as the current element to be sorted.
- Compare with previous elements: Compare the current element with its predecessor. If the current element is smaller than its predecessor, compare it with the element before. continue moving backward until you find the appropriate position for the current element.
- Insert the current element: Once the correct position is found, insert the current element and shift the other element to the right to make space if necessary.
- Repeat for call element: Repeat the process for each element in the list, moving through the list one element at a time. until the entire list is sorted.
WAP for Insertion Sort in C
#include <stdio.h>
void insertionSort(int array[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = array[i];
j = i - 1;
while (j >= 0 && array[j] > key)
{
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
void main()
{
int array[] = {90, 75, 87, 48, 2, 67, 23, 56, 98, 78, 67, 56};
int n = sizeof(array) / sizeof(array[0]);
printf("Array before sorting\n");
for (int i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
insertionSort(array, n);
printf("\nArray after sorting\n");
for (int i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
}
Output
Explanation of above C Code
- The insertionSort function takes an array and its length as a parameter.
- It iterates from the second element to the last element of the array.
- For each element, it finds the correct position in the already sorted part of the array and moves it there.
Time Complexity of Insertion Sort
The time complexity of insertion sort varies depending upon the input arrays’ initial orders.
- Best Case: The time complexity of the Insertion sort in the best case is
O(n). The best case occurs when the array is already sorted. In this scenario the insertion sort algorithm only makes a single comparision per element. - Average and Worst Case: The time complexity of the Insertion sort in the average and worst cases is
O(n^2).
Insertion sort simplicity, coupled with its efficiency for small and nearly data sets, makes it a valuable algorithm for certain applications.
Happy Coding & Learning
2 thoughts on “WAP for Insertion Sort in C”