# Algorithm and Example of Insertion Sort - Ishwaranand

## 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 is itself sorted. And remaining elements are unsorted.

Pass1:  Data is inserted either before Data or after Data so that Data and Data are sorted.

Pass2: Data is inserted to its proper position in Data Data so the Data, Data and Data are sorted.

Pass3: Data is inserted to its proper position in Data, Data, Dataso that Data, Data, Data and Data are sorted.
.
.
.
PassN-1: Data[N] is inserted in Data, Data...Data[N-1] so that Data, Data...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 is sorted and the remaining list is unsorted.

123456
503010406020

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

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

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