# Algorithm and Example of Insertion Sort

## Insertion Sort

**Q) Explain the Insertion sort algorithm with a suitable example.**

- Insertion sort is based on the principle of inserting the element to the proper position in the previously sorted list. if take (N-1)passes to sort N element of the array.
- In this sort, the first element is considered to be sorted and the remaining elements are in the unsorted list. One element from the unsorted list is picked-up and inserted in the sorted list to its proper position. This process is continued until the unsorted list is finished.

**Initially:**Data[1] is itself sorted. And remaining elements are unsorted.

**Pass1:**Data[2] is inserted either before Data[1] or after Data[1] so that Data[1] and Data[2] are sorted.

**Pass2:**Data[3] is inserted to its proper position in Data[1] Data[2] so the Data[1], Data[2] and Data[3] are sorted.

**Pass3:**Data[4] is inserted to its proper position in Data[1], Data[2], Data[3]so that Data[1], Data[2], Data[3] and Data[4] are sorted.

.

.

.

**PassN-1:**Data[N] is inserted in Data[1], Data[2]...Data[N-1] so that Data[1], Data[2]...Data[N] are sorted.

Image Source ~ Crafted With ©Ishwaranand - 2020 ~ Image by ©Ishwaranand |

**Algorithm: Insertion_sort(Data[],N)**

- This is the algorithm for inserted sort to sort the array in ascending order.
- Data[]-Array of elements
- N-size ofarray
- i,j-index variable
- temp-temporary variable

Step 1 : Start

Step 2 : Repeat the steps 3, 4, 5 and 6 for i = 2 to N

Step 3 : Set temp = Data[i]

Step 4 : Set j = i - 1

Step 5 : Repeat while j > 0 and temp < data[i]

a) Set Data[j+1] = Data[j]

b) Set j = j - 1

Step 6 : Set Data[j+1] = temp

Step 7 : Stop

**Example Insertion Sort**

Consider the following array with

**6**elements.Red is Sorted

**Black**is unsorted

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

50 | 30 | 10 | 40 | 60 | 20 |

**Initially:**Consider data[1] is sorted and the remaining list is unsorted.

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

50 | 30 | 10 | 40 | 60 | 20 |

Pass 1 : As Data[2] < Data[1] hence, insert Data[2] before Data[1]

**Before Insertion**

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

50 | 30 | 10 | 40 | 60 | 20 |

**After Insertion**

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

30 | 50 | 10 | 40 | 60 | 20 |

Pass 2 : As Data[3] < Data[2], Data[1] hence, insert Data[3] before Data[1]

**Before Insertion**

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

30 | 50 | 10 | 40 | 60 | 20 |

**After Insertion**

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

10 | 30 | 50 | 40 | 60 | 20 |

Pass 3 : As Data[4] < Data[3], hence, insert Data[4] before data[3]

**Before Insertion**

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

10 | 30 | 50 | 40 | 60 | 20 |

**After Insertion**

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

10 | 30 | 40 | 50 | 60 | 20 |

Pass 4 : As data[5] > Data[4], hence, Data[5] remain at the same position

**Before Insertion**

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

10 | 30 | 40 | 50 | 60 | 20 |

**After Insertion**

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

10 | 30 | 40 | 50 | 60 | 20 |

Pass 5 : Data[6] < Data[5], Data{4], Data[3], Data[2] hence, Data[6] is before Data[2]

**Before Insertion**

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

10 | 30 | 40 | 50 | 60 | 20 |

**After Insertion**

1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|

10 | 20 | 30 | 40 | 50 | 60 |

## No comments

Comment on Ishwaranand or Happy Day

Not, Add any types of links