Insertion sort is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be inserted in this sorted sub-list, has to find its appropriate place and then it is to be inserted there. Hence the name insertion sort.
We have already discussed some basics of insertion sort in the previous chapter Insertion Sort. In this chapter, we will discuss insertion sort in more detail.
#include<stdio.h>
#include <stdbool.h>
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count) {
int i;
for(i = 0;i < count-1;i++) {
printf("=");
}
printf("=\n");
}
void display() {
int i;
printf("[");
// navigate through all items
for(i = 0;i < MAX;i++) {
printf("%d ",intArray[i]);
}
printf("]\n");
}
void insertionSort() {
int valueToInsert;
int holePosition;
int i;
// loop through all numbers
for(i = 1; i < MAX; i++) {
// select a value to be inserted.
valueToInsert = intArray[i];
// select the hole position where number is to be inserted
holePosition = i;
// check if previous no. is larger than value to be inserted
while (holePosition > 0 && intArray[holePosition-1] > valueToInsert) {
intArray[holePosition] = intArray[holePosition-1];
holePosition--;
printf(" item moved : %d\n" , intArray[holePosition]);
}
if(holePosition != i) {
printf(" item inserted : %d, at position : %d\n" , valueToInsert,holePosition);
// insert the number at hole position
intArray[holePosition] = valueToInsert;
}
printf("Iteration %d#:",i);
display();
}
}
int main()
{
printf("Input Array: ");
display();
printline(50);
insertionSort();
printf("Output Array: ");
display();
printline(50);
return 0;
}
Input Array: [4 6 3 2 1 9 7 ]
==================================================
Iteration 1#:[4 6 3 2 1 9 7 ]
item moved : 6
item moved : 4
item inserted : 3, at position : 0
Iteration 2#:[3 4 6 2 1 9 7 ]
item moved : 6
item moved : 4
item moved : 3
item inserted : 2, at position : 0
Iteration 3#:[2 3 4 6 1 9 7 ]
item moved : 6
item moved : 4
item moved : 3
item moved : 2
item inserted : 1, at position : 0
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
item moved : 9
item inserted : 7, at position : 5
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
Insertion sort is a very simple method to sort numbers in an ascending or descending order. This method follows the incremental method. It can be compared with the technique how cards are sorted at the time of playing a game.
The numbers, which are needed to be sorted, are known as keys. Here is the algorithm of the insertion sort method.
Input − An array of data, and the total number in the array
Output --The sorted Array
Begin
for i := 1 to size-1 do
key := array[i]
j := i
while j > 0 AND array[j-1] > key do
array[j] := array[j-1];
j := j – 1
done
array[j] := key
done
End
This sorting technique is similar with the card sorting technique, in other words, we sort cards using insertion sort mechanism. For this technique, we pick up one element from the data set and shift the data elements to make a place to insert back the picked up an element into the data set.
Run time of this algorithm is very much dependent on the given input.
If the given numbers are sorted, this algorithm runs in O(n) time. If the given numbers are in reverse order, the algorithm runs in O(n2) time.
The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n2), where n is the number of items.
As we mentioned above that insertion sort is an efficient sorting algorithm, as it does not run on preset conditions using for loops, but instead it uses one while loop, which avoids extra steps once the array gets sorted.
Even though insertion sort is efficient, still, if we provide an already sorted array to the insertion sort algorithm, it will still execute the outer for loop, thereby requiring n steps to sort an already sorted array of n elements, which makes its best case time complexity a linear function of n.
Data Structures
Data Structures Overview Arrays Linked List Stack Queue Priority QueueExpression parsing
Infix Notation Prefix Notation Postfix notation Notation ConversionHashing
Hash Table and Function Collision ResolutionSearching Techniques
Linear Search Binary Search Interpolation Search Fibonacci SearchSorting
Bubble Sort Bubble Sort in Depth Selection Sort Selection Sort in Depth Insertion Sort Insertion Sort in Depth Shell Sort Merge Sort Quick Sort Quick Sort in Depth Counting Sort Radix Sort Bucket SortTree
Trees and Graphs Binary Tree Types of Binary Trees Binary Search Tree N-ary Tree AVL Tree Red Black Tree Splay tree B tree B+ treeTree Search Traversal Techniques
Breadth First Search (BFS) Depth First Search (DFS) Inorder, Preorder and Postorder TraversalHeaps
Heaps Introduction Binary Heap Heap OperationsTrending
C Programming
Remember to follow community guidelines and don't go off topic.