In this article Insertion Sort in C we give the information about in insertion sort, the element is inserted before or after and the comparison is started from the first elements.
Insertion Sort in C:
Insertion sort is implemented by inserting particular elements at the proper position. In insertion sort, the element is inserted before or after and the comparison is started from the first elements.
Since a first element has no other elements before it, so it does not require any comparison. Second elements requires 1 comparison, 3rd require 2 comparisons, 4th requires 3 comparisons and so on. The last elements require n-1 comparisons.
Consider an array with n elements. The process of insertion each element at proper place is as follows:
Iteration 1: a[0] is already sorted because of only one element.
Iteration 2: a[1] is inserted before or after a[0]. So a[0] & a[1] are sorted.
Iteration 3: a[2] is inserted before a[0], in-between a[0], a[1], or after a[1]. So a[0], a[1] & a[2] are sorted and so on.
Algorithm:
Step 1: start
2: Read n element of an array a.
3: Let i=0
4: Let j=0
5: if(a[j]>a[i]) then
temp = a[j]
a[j]=a[i]
6: let k=i
7: a[k] = a [k-1]
8: Calculate k=k-1
9: if k>j then go to step 7
10: a[k+1]=temp
11: calculate j=j+1
12: if j<I then go to step 5
13: i=i+1
14: printf sorted array
15: stop
Example:
Consider array elements as 29, 21, 37, 17, 5
Iteration 1:
| 29 | 21 | 37 | 17 | 5 |
Insert 21 at 0th position as 29>21 and shift 29 right by one position
| 21 | 29 | 37 | 17 | 5 |
Iteration 2:
| 21 | 29 | 37 | 17 | 5 |
No change as 21 < 29
| 21 | 29 | 37 | 17 | 5 |
No change 29<37
Iteration 3:
| 21 | 29 | 37 | 17 | 5 |
Insert 17 at 0th position as 17<21 and shift all elements to right by one position
| 17 | 21 | 29 | 37 | 5 |
No change as 21<37
| 17 | 21 | 29 | 37 | 5 |
No change 29<37
Iteration 4:
| 17 | 21 | 29 | 37 | 5 |
Insert 5 at 0th position as 5<17 and shift all elements to right by one position.
| 5 | 17 | 21 | 29 | 37 |
No change 17<37
| 5 | 17 | 21 | 29 | 37 |
No change 21<37
| 5 | 17 | 21 | 29 | 37 |
No change 29<37
The Sorted list is as follows:
| 5 | 17 | 21 | 29 | 37 |
/* C Program to sort an array in ascending order using Insertion Sort */
int main()
{
int i, j, temp;
int arr[6]={34, 2, 15, 56, 26, 4};
printf(“\n Insertion Sort ”)
printf(“\n Unsorted List of Array : “);
for(i=0;i<6;i++)
printf(“\t %d”,arr[i]);
for (i = 1 ; i <6 ; i++)
{
j = i;
while ( j > 0 && arr[j-1] > arr[j])
{
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j–;
}
}
printf(“\nSorted list in ascending order:”);
for (i = 0; i <6; i++)
{
printf(“\t%d”, arr[i]);
}
return 0;
}
Output:
Insertion Sort
Unsorted List of Array : 34 2 15 56 26 4
Sorted list in ascending order: 2 4 15 26 34 56
Some More:
POP- Introduction to Programming Using ‘C’
OOP – Object Oriented Programming
DBMS – Database Management System
RDBMS – Relational Database Management System
Join Now: Data Warehousing and Data Mining