# Algorithm and Example of Insertion Sort - Ishwaranand

Follow Your Dream | Believe in YourSelf | & Don't Give Up

## 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

123456
503010406020

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

123456
503010406020

Pass 1 : As Data[2] < Data[1] hence, insert Data[2] before Data[1]
Before Insertion
123456
503010406020
After Insertion
123456
305010406020
Pass 2 : As Data[3] < Data[2], Data[1] hence, insert Data[3] before Data[1]
Before Insertion
123456
305010406020
After Insertion
123456
103050406020

Pass 3 : As Data[4] < Data[3], hence, insert Data[4] before data[3]
Before Insertion
123456
103050406020
After Insertion
123456
103040506020
Pass 4 : As data[5] > Data[4], hence, Data[5] remain at the same position
Before Insertion
123456
103040506020
After Insertion
123456
103040506020

Pass 5 : Data[6] < Data[5], Data{4], Data[3], Data[2] hence, Data[6] is before Data[2]
Before Insertion
123456
103040506020
After Insertion
123456
102030405060