## Java, J2EE & SOA Certification Training

- 35k Enrolled Learners
- Weekend
- Live Class

C Programming and Data Structures (41 Blogs)

Insertion Sort in C is a simple and efficient sorting algorithm, that creates the final sorted array one element at a time. It is usually implemented when the user has a small data set. I’ll cover the following topics:

- What is Insertion Sort?
- Brief Working and Complexity
- Algorithm for Insertion Sort in C
- Insertion Sort in C

Insertion Sort is a sorting algorithm where the array is sorted by taking one element at a time. The principle behind insertion sort is to take one element, iterate through the sorted array & find its correct position in the sorted array.

Insertion Sort works in a similar manner as we arrange a deck of cards.

In each iteration, it compares the current element with the values in the sorted array. If the current element is greater than the element in the array, then it leaves the element and iterates to the next array element. Otherwise, if the current element is smaller than the array element then it moves the rest of the element in the array by one position and makes space for the current in the sorted array.

This is how Insertion sort takes one input elements at a time, iterates through the sorted sub-array and with each iteration it inserts one element at its correct position. This is why the algorithm is known as Insertion sort.

As the average & worst-case complexity of this algorithm are **O(n2)**, where n is the number of elements, Insertion sort is not good for large data sets.

**Step 1**− If the element is the first one, it is already sorted.**Step 2**– Move to next element**Step 3**− Compare the current element with all elements in the sorted array**Step 4**– If the element in the sorted array is smaller than the current element, iterate to the next element. Otherwise, shift all the greater element in the array by one position towards the right**Step 5**− Insert the value at the correct position**Step 6**− Repeat until the complete list is sorted

To understand how Insertion sort works, refer to the below image.

Let’s understand how insertion sort is working in the above image.

**122**, 17, 93, 3, 36

for i = 1(2nd element) to 36 (last element)

i = 1. Since 17 is smaller than 122, move 122 and insert 17 before 122

**17, 122**, 93, 3, 36

i = 2. Since 93 is smaller than 122, move 122 and insert 93 before 122

**17, 93,122**, 3, 36

i = 3. 3 will move to the beginning and all other elements from 17 to 122 will move one position ahead of their current position.

**3, 17, 93, 122,**36

i = 4. 36 will move to position after 17, and elements from 93 to 122 will move one position ahead of their current position.

**3, 17, 36, 93 ,122**

Now that we have understood how Insertion Sort works, let us quickly look at a C code to implement insertion sort

**Insertion Sort Function**

void insertionSort(int array[], int n) { int i, element, j; for (i = 1; i < n; i++) { element = array[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key by one position */ while (j >= 0 && array[j] > element) { array[j + 1] = array[j]; j = j - 1; } array[j + 1] = element; } }

#include <math.h> #include <stdio.h> // Insertion Sort Function void insertionSort(int array[], int n) { int i, element, j; for (i = 1; i < n; i++) { element = array[i]; j = i - 1; while (j >= 0 && array[j] > element) { array[j + 1] = array[j]; j = j - 1; } array[j + 1] = element; } } // Function to print the elements of an array void printArray(int array[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", array[i]); printf("n"); }

Now after executing the above C program you would have understood how Insertion Sort works & how to implement it in C language. I hope this blog is informative and added value to you. With this, we come to an end of this Insertion Sort in C article.

C*heck out the Java training*

REGISTER FOR FREE WEBINAR

Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP