Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as Quicksort, heapsort, or Merge sort. However, insertion sort provides several advantages:
- Simple implementation
- Efficient for (quite) small data sets
- Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
- More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
- Stable; i.e., does not change the relative order of elements with equal keys
- In-place; i.e., only requires a constant amount O(1) of additional memory space
- Online; i.e., can sort a list as it receives it
Step-by-step example:
The following table shows the steps for sorting the sequence {3, 7, 4, 9, 5, 2, 6, 1}. In each step, the item under consideration is underlined. The item that was moved (or left in place because it was biggest yet considered) in the previous step is shown in bold.
3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 5 7 9 2 6 1
2 3 4 5 7 9 6 1
2 3 4 5 6 7 9 1
1 2 3 4 5 6 7 9
Algorithm/Pseudo-Code:
for i ← 1 to i ← length(A)-1
{
//The values in A[ i ] are checked in-order, starting at the second one
// save A[i] to make a hole that will move as elements are shifted
// the value being checked will be inserted into the hole's final position
valueToInsert ← A[i]
holePos ← i
// keep moving the hole down until the value being checked is larger than
// what's just below the hole <!-- until A[holePos - 1] is <= item -->
while holePos > 0 and valueToInsert < A[holePos - 1]
{ //value to insert doesn't belong where the hole currently is, so shift
A[holePos] ← A[holePos - 1] //shift the larger value up
holePos ← holePos - 1 //move the hole position down
}
// hole is in the right position, so put value being checked into the hole
A[holePos] ← valueToInsert
}
Here is the C Code for Insertion Sort:
/* Double-Click To Select Code */
#include<stdio.h>
#include<conio.h>
void sort(int arr[],int n); //Function Prototype
void main()
{
int arr[20],i,n,j,k;
clrscr();
printf("\nEnter the number of elements in the array: ");
scanf("%d",&n);
printf("\nEnter the elements of the array");
for(i=0 ; i < n ; i++)
{
printf("\n arr[%d] = ",i);
scanf("%d",&arr[i]);
}
sort(arr,n);
printf("\nThe sorted array is: \n");
for(i=0;i<n;i++)
printf("%d\t",arr[i]);
getch();
}
void sort(int arr[],int n)
{
int k,j,temp;
for(k=1 ; k < n ; k++)
{
temp=arr[k];
j=k-1;
while((temp < arr[j]) && (j>=0))
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}
}
Output:
This article uses material from the Wikipedia article Insertion_sort which is released under the Creative Commons Attribution-Share-Alike License 3.0
Do you like this post? Please link back to this article by copying one of the codes below.
URL: HTML link code: Forum link code: