Insertion Sort in C: Insertion Sort is the very simple and adaptive sorting techniques, widely used with small data items or data sets. It’s more efficient with the partially sorted array or list, and worst with the descending order array and list. Below is the Table of content what we are going to learn in this complete article.

**Table of Content**

- Advantages and Disadvantages of Insertion Sort
- Real Life Example
- Pseudocode of Insertion Sort
- Complexity
- C Program for Insertion Sort using For Loop
- Insertion Sort using While Loop
- C Program for Insertion Sort using Functions
- The output of Each Program
- Analaysis of Output

**How does Insertion Sort Work?**

Insertion sort is a sorting technique, which use to sort the data in ascending or descending order, like another sorting technique (Selection, Bubble, Merge, Heap, QuickSort, Radix, Counting, Bucket, ShellSort, and Comb Sort).

It’s very useful with small data set or partially sorted data and not efficient if data is sorted in descending order and you want to sort data in ascending order.

The implementation is very easy, Jon Bentley implements in just 3 steps and the optimize version in just 5 steps.

**Advantages of Insertion Sort**

There are many advantages, below is the list of all advantages.

- implementation is very simple
- It’s very efficient for smaller data
- It is more efficient or better compare to Selection Sort and Bubble Sort
- it’s adaptive when a partially sorted array or list is provided as input.
- Its space complexity is very less O(1).
- It is a stable sorting technique
- It is a stable technique, as it does not change the relative order of elements which are equal.

**Disadvantages of Insertion Sort**

As we know that all sorting algorithms have some disadvantage so insertion sort also has, there are a few lists of demerits of insertions sort

- Not efficient for larger lists.
- It does not perform as other sorting algorithms perform.
- It is only useful for the few data list or if an array is mostly sorted.

**Real-Life Example**

While playing a card we use insertion sort, when 4 players are played and all of them have 13 cards, after that they arranged the card according to colour, type, of ascending or descending order, it’s totally depends on the players habits but one thing is clear they pick a card from the 13 and set the card in the correct position.

**Pseudocode of Insertion Sort**

```
i ← 1
while i < length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
i ← i + 1
end while
```

**The Complexity**

Sr. No. | Complexity | Time | Space |

1 | Best-Case | О(n) | – |

2 | Average Case | О(n^2) | – |

4 | Worst-Case | О(n^2) | – |

5 | Space Complexity | – | О(n) Total, O(1) Auxiliary |

All the solutions are tested on **Dev-C++** and online compilers, If you still face any issue comment below we will help you on the spot.

**Insertion Sort Using For Loop**

/* C Program for Insertion Sort Using FOR Loop */ #include <stdio.h> int main() { /* "Insertion Sort in C Program". This Programming Solution is belong to Simple Categories in C Language. -by https://tutorialsbookmarks.com */ int number, i, j, temp, count=0; printf("Enter How Many Numbers You Want to Sorted: "); scanf("%d", &number); /* Array Size is equal to the numbers you entered, by using this method we can save the size. */ int a[number]; printf("\n\nEnter the Numbers: "); /* Storing Numbers in an Array */ for(i = 0; i < number; i++) { scanf("%d", &a[i]); } /* Sorting Numbers by using Insertion Sort */ for(i = 1; i <= number - 1; i++) { for(j = i; j > 0 ; j--) { if (a[j - 1] > a[j]) { temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; /* For Counting Total Number of Iterations */ count++; } } } printf("\n\nSorting Result in Ascending order of Insertion Sort: "); for(i = 0; i < number; i++) { printf(" %d ", a[i]); } /* For printing, the array insertion sort results in Descending order remove this comment printf("\n\nSorting Result in Descending order of Insertion Sort: "); for(i = number-1; i >= 0; i--) { printf(" %d ", a[i]); } */ printf("\n\n"); printf("Total Number of Iterations Needed %d", count); printf("\n\n"); return 0; }

**The Output**

**Insertion Sort Using While Loop**

/* C Program for Insertion Sort While loop*/ #include <stdio.h> int main() { /* "Insertion Sort in C Program". This Programming Solution is belong to Simple Categories in C Language. -by https://tutorialsbookmarks.com */ int number, i, j, temp, count=0; printf("Enter How Many Numbers You Want to Sorted: "); scanf("%d", &number); /* Array Size is equal to the numbers you entered, by using this method we can save the size. */ int a[number]; printf("\n\nEnter the Numbers: "); /* Storing Numbers in an Array */ for(i = 0; i < number; i++) { scanf("%d", &a[i]); } /* Sorting Numbers by using Insertion Sort */ i = 1; while( i <= number - 1) { j = i; while( j > 0 && a[j - 1] > a[j]) { temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; j--; count++; } i++; } printf("\n\nSorting Result in Ascending order of Insertion Sort: "); for(i = 0; i < number; i++) { printf(" %d ", a[i]); } /* For printing, the array insertion sort results in Descending order remove this comment printf("\n\nSorting Result in Descending order of Insertion Sort: "); for(i = number-1; i >= 0; i--) { printf(" %d ", a[i]); } */ printf("\n\n"); printf("Total Number of Iterations Needed %d", count); printf("\n\n"); return 0; }

**The Output**

**Insertion Sort Program Using Functions in C**

/* C Program for Insertion Sort Using Functions*/ #include <stdio.h> void insertion(int a[], int number) { int i, j, temp; int count=0; for(i = 1; i <= number - 1; i++) { for(j = i; j > 0 ; j--) { if (a[j - 1] > a[j]) { temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; /* For Counting Total Number of Iterations */ count++; } } } printf("\n"); printf("\nTotal Number of Iterations Needed %d", count); } int main() { /* "Insertion Sort in C Program". This Programming Solution is belong to Simple Categories in C Language. -by https://tutorialsbookmarks.com */ int number, i, j, temp; printf("Enter How Many Numbers You Want to Sorted: "); scanf("%d", &number); /* Array Size is equal to the numbers you entered, by using this method we can save the size. */ int a[number]; printf("\n\nEnter the Numbers: "); /* Storing Numbers in an Array */ for(i = 0; i < number; i++) { scanf("%d", &a[i]); } insertion(a, number); printf("\n\nSorting Result in Ascending order of Insertion Sort: "); for(i = 0; i < number; i++) { printf(" %d ", a[i]); } /* For printing, the array insertion sort results in Descending order remove this comment printf("\n\nSorting Result in Descending order of Insertion Sort: "); for(i = number-1; i >= 0; i--) { printf(" %d ", a[i]); } */ printf("\n\n"); return 0; }

**The Output**

**Step by Step Analysis**

Let’s take an example for the Insertion sorting, As shown in Given GIF picture. Let’s understand the given example of the output of the program Step by Step.

So this is our Input or data stored in an array, and we have to sort the array, let understand how it works.

**Keynote:** Always remember Insertion Sort always start with 1 index(Not 0), If your array starts with the index 1 then it will start with index 2, always start with the new element of starting index of an Array or Data sets.

**Example input: 6 5 3 1 8 7 2 4**

- So here 6 is in 0’th Index
- 5 is in 1’th Index
- 3 is in 2’th Index
- 1 is in 3’th Index
- 8 is in 4’th Index
- 7 is in 5’th Index
- 2 is in 6’th Index
- 4 is in 7’th Index

**First Iterations**

Now the Our array will start from Index 1 which means the array will start from the number 5, Now So we compare the second index with the first index we can clearly see that the 5 is less than the number 6 so we just swap the number, So now our array looks like a

**5 6 3 1 8 7 2 4**

**Second Iterations**

Now Our first array index is in number 3, so again we are going to compare the number 3 to left most numbers 5 and 6 as we know that the 3 is less than the 5, and 6 so we put the number 3 before the 5 so our array will be

**3 5 6 1 8 7 2 4**

**Third Iterations**

Again repeat the same step so now compare to 1 to it left most items. So our new array will be

**1 3 5 6 8 7 2 4**

**Forth Iterations**

Repeat a previously step again as we can see that 8 is greater then all left most items, so we are not going to make any changes in an array. our array will be the same

**1 3 5 6 8 7 2 4**

**Fifth Iterations**

In Fifth Iterations repeat the same step now 7 is less than the 8 so we swap the position with 8. Now our new array will be

**1 3 5 6 8 7 2 4**

**Sixth Iterations**

Now we just change the number 2 location with its appropriate location.

**1 2 3 5 6 7 8 4**

**Seventh Iterations**

This is the last iteration for the array we just need to find the correct location of the number 4 and put the number on the right location.

**1 2 3 4 5 6 7 8**

So we need a total of 7 Iterations(for topmost Loop) for this example, and for Nested or inner loop we need total 15 Total numbers of Iterations.

**Frequently Asked Questions**

**Can you implement insertion sort for sorting linked lists?**The answer is, **yes**, you can implement insertion sort on a linked list.

**What will be time complexity of insertion sort if the array is already sorted?****O(n)**, If the array is already sorted.

**What is the time complexity of insertion sort for an unsorted list?****O(n^2)**, Worst-case and average-case complexity are the same.

**What are the Arithmetic Operators in C**?Please see this guide for a complete explanation for arithmetic operators in C language

Thanks for the information

Comments are closed.