Algorithm (Lab report 03)

Theory: Insertion sort is a sorting algorithm with an O(n^2) running time. Although the worst case run time is the same as bubble sort, but it is a lot more applicable for smaller data sets. To understand this algorithm, it is very similar to how some people sort their hand of cards.

Here is how it works, we loop through the array. For each item in the array, the left side of the array is sorted and the right side is unsorted. We will take that item and put it in the appropriate spot then move on to the next item in the array.

Apparatus:

            i.   Computer.

           ii.   Coding Language.

          iii.   Compiler (Code block, Dev c/c++, Turbo c/c++ etc.)

          iv.    Coding skill.

Algorithm: ( Insertion sort)

Step 01: Algorithm for j to 2 to length[A]
Step 02: do key to A[j]
Step 03: Insert A[j] into the sorted sequence A[1….j-1]
Step 04: i to j-1
Step 05: while i>0 and A[i]>key
Step 06       do A[i+1] to A[i]
Step 07:          I to i-1
Step 08:      A[i+1] to key

Source code: (Insertion sort)

# include<stdio.h>
int main()
{
int A[20], N, Temp, i, j;      
scanf("%d", &N);
for(i=0; i<N; i++)
scanf("%d", &A[i]);
for(i=1; i<N; i++)
    {
    Temp = A[i];
    j = i-1;
    while(Temp<A[j] && j>=0)
        {
        A[j+1] = A[j];
        j = j-1;
        }
    A[j+1] = Temp;
    }
for(i=0; i<N; i++)
printf("%d ", A[i]);
return 0;
}

Result:

Sample Input                                           Sample output

5
5  4  1  2  3                                                1  2  3  4  5

7
1  4  2  5  6  1  7                                        1  1  2  4  5  6  7

8
2  3  6  5  34  11  12  15                          2  3  5  6  11  12  15  34

Caution: You must change this code. And also change the test value when you print it......Try to make change or modify this.