# Insertion Sort ## Insertion Sort

• An insertion sort is one that sorts a set of values by inserting values into an existing sorted ﬁle.
• Suppose that Iist[] is a list of n elements in memory. The insertion sort technique scans the list Iist[] from Iist to list[n-1], inserting each element list[ k] into its proper position in the previously sorted sublist list[o], list, ..., list[n-1].

#### Illustration:

Let list[] be an array of 7 elements: 25, 15, 30, 9, 99, 20, 26.
Initial scenario,

Step 1: list

Step 2: list>list , so position of elements remain same.

Step 3: list is less than list[2.],list  and list[o], thus list is inserted at list[o] position and others are shifted by one position.

Step 4: list>list , so position of elements remain same.

Step 5: list is less than list, list, and list, so list is inserted at the position of list and others are shifted by one position.

Step 6: list is less than list and list, so list is inserted at the position of list and others are shifted by one position.
After step 6, the list is completely sorted.

### Algorithm for insertion sort:

This algorithm sorts the array list with n elements. Let temp be a temporary variable to interchange the two values, k be the total
number of passes and j be another control variable for sorting.
Step1: Initialization,
Set k=1

Step2: For k=1 to (n-1)
Set temp=a.[k]
Set j=k-1
While temp<a[j] and (j>=0) perform the following steps
Set a[j+1]=a[j]
Set j=j-1
[End of loop structure]
Assign the value of temp to list[j+1]
[End of for loop structure]

Step3: Exit

### Efficiency of insertion sort

Best Case: If the initial list is already sorted, then only one comparison is made on each pass, so that the complexity comes out to be O( n ).
Worst Case: If the initial list is sorted in reverse order, the total number of comparisons is:
1+z+3+...+k+(n-1)=n*(n-1)/2
so that the complexity comes out to be O(n^2).
Average Case: The average number of comparisons in the insertion sort (by considering all possible permutations of the input list) is O(n^2).
Note: The closer the list is in sorted order, the more efficient the insertion sort is.

### C Program For Insertion Sort

```#include <stdio.h>

void insertionSort(int arr[], int n)

{

int i, key, j;

for (i = 1; i < n; i++)

{

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key)

{

arr[j + 1] = arr[j];

j = j - 1;

}

arr[j + 1] = key;

}

}

void printArray(int arr[], int n)

{

int i;

for (i = 0; i < n; i++)

printf("%d  ", arr[i]);

printf("\n");

}

int main()

{

int arr,n,i;

printf("How many elements are u going to enter?: ");

scanf("%d",&n);

printf("Enter %d elements:\n",n);

for(i=0;i<n;i++)

scanf("%d",&arr[i]);

insertionSort(arr, n);

printf("\nThe sorted list is:\n");

printArray(arr, n);

return 0;

}```

### Related Posts

Bubble Sort

Merge Sort

Selection Sort

Quick Sort

C Program For Selection Sort | C Programming

C Program For Quick Sort | C Programming

C Program For Merge Sort | C Programming

C Program For Bubble Sort | C Programming

C Program for Insertion Sort | C Programming