In this blog, we will explore the concept of Insertion Sort in C, one of the simplest sorting algorithms used in computer science. We will explain how the algorithm works and provide a step-by-step example of its implementation in the C programming language. By the end of this blog, you will have a clear understanding of how Insertion Sort functions and how you can use it to sort data in your own programs. Whether you are a beginner programmer or an experienced developer, this blog will provide you with valuable insights into the world of sorting algorithms.
In this article we will study sorting with reference to C. There are two types of sorting –
1.Insertion Sort
2.Bubble Sort
We’ll look deep into Insertion sort through this article.
Insertion Sort in C
In C, the “insertion sort” method divides an array into parts that are already sorted and parts that aren’t. It then takes the appropriate values from the unsorted parts and places them in the proper locations in the sorted parts.
The insertion sort employs the following algorithm to arrange a list of sizes in ascending order:
1. Begin at arr[1] and work your way through arr[n] until you reach arr[n].
2. Contrast the key with the last thing you examined.
3. Compare the sizes of the parts of the essential element to the sizes of their predecessors. Move the larger elements up one position to make room for the new element.
Insertion Sort in C Algorithm Pseudo-code
Consider the first part as having been completed (a single element is always sorted)
- Select arr[1] and store it in a temporary variable.
- Begin with the items on the back of the sorted section and compare their values to those in tmp.
- If arr[k] is less than tmp, it should be moved to index k+1.
- This will continue until the correct location is found. The temporary piece will then be returned to its proper place.
- When we’ve completed this for all elements, we’ll have the desired array, with the elements arranged in ascending order.
Explanation
First iteration:
- Initially, the first element is sorted, i points to the second element i.e. 33. Now j points to the 45. After running the while loop, j = -1, cur = 33,
While Loop:
- At the end of for loops iteration we place cur at its position i.e. j+1 = 0 and the array becomes
Second iteration:
- Now I point to 2 and j points to 33. After execution of the while loop
While Loop:
- arr[j] = cur
Third iteration: At the beginning of the third iteration,
- cur = 60, j points to 45, 60 is greater than 45 and thus, we are not required to modify anything in this iteration.
Fourth iteration:
- At the beginning of the fourth iteration,
- Now, cur = 71, j is 60 which is less than 71. Thus, again the array is sorted so far.
Fifth iteration:
- Array at the beginning of the fifth iteration:
- Lastly, i points to 29 i.e. cur = 29 and j = 4 i.e. 71. Variation during the while loop in the array is as follows:
- Now cur must be placed at position 4.
Insertion sort in c
Insertion Sort(arr, size)
consider 0th element as sorted part
for each element from i=2 to n-1
tmp = arr[i]
for j=i-1 to 0
If a[j]>tmp
Then right shift it by one position
put tmp at current j
You Must Like: Python Functions: The Best Guide for You
Insertion Sort in C Example
Program: Write a program to implement insertion sort in C language.
using System;
class Insertion {
static void insert(int[] a) /* function to sort an aay with insertion sort */
{
int i, j, temp;
int n = a.Length;
for (i = 1; i < n; i++) {
temp = a[i];
j = i – 1;
while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position ahead from their current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}
static void printArr(int[] a) /* function to print the array */
{
int i;
int n = a.Length;
for (i = 0; i < n; i++)
Console.Write(a[i] + ” “);
}
static void Main() {
int[] a = { 98, 54, 53, 18, 21, 12 };
Console.Write(“Before sorting array elements are – \n”);
printArr(a);
insert(a);
Console.Write(“\nAfter sorting array elements are – \n”);
printArr(a);
}
}
Output:
Conclusion
- The insertion sort algorithm is one of the most basic arrays sorting methods.
- It’s simple to accomplish using for and while loops.
- It performs well with small amounts of data and partially sorted data.
