Q. Explain the insertion sort with a proper algorithm. What is the complication of insertion sort in the worst case?
Ans:
Insertion Sort technique: One of the easiest sorting algorithms is the insertion sort.
Insertion sort comprises of n - 1 passes. For pass p = 2 through n, insertion sort assures that the elements in the positions 1 through p are in sorted order. Insertion sort makes use of the fact those elements in positions 1 through p - 1 are already known in the sorted order.
Void insertion_sort( input_type a[ ], unsigned int n )
{
unsigned int j, p;
input_type tmp;
a[0] = MIN_DATA; /* sentinel */
for( p=2; p <= n; p++ )
{
tmp = a[p];
for( j = p; tmp < a[j-1]; j-- )
a[j] = a[j-1];
a[j] = tmp;
}
}
Because of the nested loops present, each of which can take n iterations, insertion sort is O(n2). Furthermore, this bound is tight, because input in reverse order can actually obtain this bound. A precise calculation shows that the test at line 4 can be executed at most of the p times for each value of p. By summing over all p gives a total of (n(n-1))/2 = O(n2).