# Array C Programing

This algorithm scans an array 'list' (with n element list, list , .... list[n]) from list  to list[n], inserting each element list [i] into its proper position in the previously sorted subarray list, list,......,list [i-1]. That is:

Pass 1: list  by itself is trivially sorted.

Pass 2: list  is inserted before or after list so that: list, list is sorted.

Pass 3: list  is inserted into its proper place in the list, list, that is before list, between list and list, or after list, so that: list, list, list, list is sorted.

Pass 4: list is inserted into its proper place in list, list, list, so that: list, lis, list, list, is sorted.

Pass n: list [n] is inserted into its proper place in list, list, ..., list[n-1] so that: list, list,... list[n-1], is sorted.

This algorithm is frequently using when n is small.

The problem of deciding how to insert list[i] in its proper place in the sorted subarray list, list,...,list[i-1], can be accomplished by comparing list[i] with list [i-j], comparing list[i] with [i-2], and so on, until first meeting an element list[j] such that list[j] <= list[i].

Then each of the element list[i-1], list[i -2], ..., list[j +1] is moved forward one location, and list[i] is then inserted in the j+1st position in the array. The algorithm is simplified if there always is an element list[j] such that list[j] <= list[i], otherwise, we must constantly check to see if we are comparing list[i] with list. This condition can by accomplished by using a sentinel element list = -∞ (or a very small number).

Example: The insertion sort algorithm is given below:

Algorithm: (Insertion sort) INSERTION (list, n)

This algorithm sorts the array list with n elements;

Step 1: set list: =-∞ [Initialises sentinel element]

Step 2: Repeat Step 3 to 5 for i = 1,2,... n

Step 3: set temp: - list[i], and, ptr: = i - 1

Step 4: Repeat while temp < list[ptr]

(a) set list[ptr + 1]: = list[ptr] [moves element forward]

(b) set ptr: = ptr -1 [End of loop]

Step 5: set list[ptr + 1]: = temp [Inserts element in proper place] [End of Step 2 loop]

Step 6: Return

Complexity of Insertion Sort:

The worst case occurs when the array 'list' is in reverse order and inner loop must use the maximum number i-1 of comparisons.

Hence, total comparisons are :
f(n) = 1 + 2 + 3 +.....+ (n - 1) =n(n-1)/2=O(n2)

In the average case there will be approximately (i - 1)/2 comparisons in the inner loop.

Hence f(n)=1/2+2/2+.....+n-1/2=n(n-1)/4=O(n2)

Thus, it is  a very slow algorithm when n is very large.