# Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

## How does the Insertion Sort work?

Suppose we have an array in unsorted order (4,6,3,1)

**1) In the first step, ** 6 will be compared with 4. Since 4 < 6 , no insertion takes place.

**2) In the second step, ** 3 will be compared with 6. Since 3 < 6 , it must be on the left of 6 . Now on left of 6 , 4 is present so 3 will be compared with 4. Since 3 < 4, 3 must be on the left of 4. As there are no more elements present to the left of 4 , 3 will be inserted before 4.

Array will look loke this => 3,4,6,1.

**3) In the third step, ** 1 will be compared with 6. Since 1 < 6 , it must be on the left of 6 . Now on left of 6 , 4 is present so 1 will be compared with 4. Since 1 < 4, 1 must be on the left of 4. Now on left of 4 , 3 is present so 1 will be compared with 3. Since 1 < 3, 1 must be on the left of 3. As there are no more elements present to the left of 3 , 1 will be inserted before 3.

Array will look loke this => 1,3,4,6.

## Insertion Program in C:-

This basic Insertion Sort in C programming explains the concept of how to sort the elements using Insertion sort in Data Structures.

#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <assert.h> void insertionSort(int N, int arr[]) { int i,j; int value; for(i=1;i=0 && value<arr[j]) { arr[j+1]=arr[j]; j=j-1; } arr[j+1]=value; for (j = 0; j < N; ++j) { printf("%d\t", arr[j]); } printf("\n"); printf("\n"); } } int main(void) { int N; scanf("%d", &N); int arr[N], i; for(i = 0; i < N; i++) { scanf("%d", &arr[i]); } printf("Input Array is: "); for(i = 0; i < N; i++) { printf("%d\t", arr[i]); } printf("\n\n"); insertionSort(N, arr); printf("Sortrd Array: \t"); for(i = 0; i < N; i++) { printf("%d\t", arr[i]); } printf("\n"); return 0; }

## Solve the Quiz of Article

**
**

**codzify.com**

Largest collection of up-to-date tutorials to learn programming languages. We are focused on easy learning. Massive collection of interview questions one may need for preparation.

**Tutorials Library**

C, C++, Java, Python Data Structures, Swift, Objective C, Swift iOS, iOS Objective C, Socket.Io, Android, Extras by Codzify.