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