Click here for a larger image.
Environment: This code might be specific to some environments, but the concept of the sorting remains the same.
Fundamental Concept
Approximately ten kinds of sorting methods are available, namely Heap, Quick, Merge, Insertion, Shell, Selection, Bubble, Linear, Address Selection, and Radix sort. Recently, when I was trying to go through the coding of an Insertion sort, I searched the Internet for the same and fortunately found some resources (U.S. universities), where the desired code was explained. I found the code a bit cumbersome to keep track of and difficult to understand (also debug), so I prepared myself for writing my own.
Prior to explaining the code, I will discuss the technique that is being applied to sort an array by using the Insertion sort method. As the name implies, the Insertion sort works on the insertion rule. In simpler terms: a number (at a current position in the array) is being compared with each of the array elements, from the begining of the list (array) until the current position. If the number is found to be less than the one already present, the element is transferred from its original position to this (new) position. That’s all, folks.
To fully understand the concept, I have created an example. Let us assume that we have an array of 10 numbers (all positive integers); in other words, 10, 9, 1, 8, 3, 7, 4, 6, 5, and 2. According to the condition explained earlier, the number 9 should be compared with 10. Because the number 9 is less than 10, we will perform a transfer operation for 9. Here comes an important step. Placing a number at the begining of the list (or somewhere else) will cause all the elements (right from the newly found location) to shift one position right. Hence, special care has been taken in the coding to perform the desired job. When we are to make a transfer, first we store the element at its current position in a temporary variable, so that when the entire list is shuffuled the element is not lost. This methodology is followed during the entire sort operation.
Thus, we see that, after the first step, our intermediatary output becomes 9, 10, 1, 8, 3, 7, 4, 6, 5, and 2. Similarly, we can trace out the entire sequence as follows:
After Iteration 1 - 9, 10, 1, 8, 3, 7, 4, 6, 5, 2
After Iteration 2 - 1, 9, 10, 8, 3, 7, 4, 6, 5, 2
After Iteration 3 - 1, 8, 9, 10, 3, 7, 4, 6, 5, 2
After Iteration 4 - 1, 3, 8, 9, 10, 7, 4, 6, 5, 2
After Iteration 5 - 1, 3, 7, 8, 9, 10, 4, 6, 5, 2
After Iteration 6 - 1, 3, 4, 7, 8, 9, 10, 6, 5, 2
After Iteration 7 - 1, 3, 4, 6, 7, 8, 9, 10, 5, 2
After Iteration 8 - 1, 3, 4, 5, 6, 7, 8, 9, 10, 2
After Iteration 9 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
In the preceding sequence of operations, numbers shown with bold and underlined formatting indicates the element transferred in that iteration. A point to be noticed here is that we require 9 iterations (in total) to sort an array of 10 elements. Thus, we can generalize this result as: We require (N-1) iterations to sort an array of N elements. The time complexity of this sorting method is the order of N2; in other words, O(N2). Though I am very well aware of the time-complexity factor, I don’t know, for the Insertion sort, how it comes to be N2. Well, this was all about the Insertion sort method. This sorting method is not the most efficient and you must use Heap, Quick, or Merge sort, the time complexity (for the average and best case) of which are NLog2N. Below, you will find the code written in C. In the coding (though it is self explainatory), the k variable denotes the position found for the current element in the array.
Source Code
#include <stdio.h>
#include <conio.h>
#define MAX 20
main()
{
static int arr[MAX];
int n, temp, pos;
int i, j, k;
printf(“Enter the number of elements : “);
scanf(“%d”, &n);
printf(“Enter the elements now :\n”);
fflush(stdin);
for (i = 0; i < n; i++)
scanf(“%d”, &arr[i]);
i = 0;
pos = 0;
for (i = 0; i < n; i = (pos + 1))
{
j = pos + 1;
/* find out the jth element’s appropriate position */
for (k = 0; arr[j] > arr[k] && (k < j); k++);
/* shift the list elements if the element’s position is
* found */
if (k < j)
{
temp = arr[j];
pos = j;
printf(“\nk = %d”, k);
for (; j >= k; j–)
arr[j] = arr[j – 1];
arr[k] = temp;
printf(“\tIntermediate o/p is : “);
for (i = 0; i < n; i++)
printf(“%2d “, arr[i]);
}
}
printf(“\n\nInsertion sorted list is : \n”);
for (i = 0; i < n; i++)
printf(“%d “, arr[i]);
getch();
}