Answer to Question #190457 in Algorithms for Sakuni Punmina

Question

Briefly describe Insertion sort algorithm using the following array of numbers. 10, 5, 15, 3, 12 ii Write an algorithm in pseudocode for the Insertion sort. (15 marks ) (10 marks) Analysing the following algorithm given in pseudocode. After executing the program what will be printed on the screen, if n-5 and elements of the array A is initialized to (10,5,15, 3, 12), Write the steps to show how you decide your answer. I/ lambda 10 an array of n Funct (A, n) for 1=n-1 to 1 for 1 to i if A1 temp Al A(j) = A(j + 1) Aff + 11 = temp for 1 - 1ton print Alil A[j+1] elements -A(1,..n) (15 marks) According to the algorithm given in the above question 1.iii, how many times will the comparison statement be executed.

Answer 1

Insertion sort:

It is the simple sorting algorithm, which array virtually split into sorted and unsorted part, The values from the unsorted part are picked and placed at the correct position in the sorted part.

Example:

The given array elements are:

10, 5, 15, 3, 12

Let the for loop initiated from i=1 to i=4, as here 10>5, hence 5 will be inserted at zeroth position and 10 will be inserted at first position.

5, 10, 15, 3, 12

No, swapping occurs because the next element already is greater than both the two elements which are before.

5, 10, 15, 3, 12

Now, here 3 is smaller than 15 hence the swapping will occurs from zeroth elements to the 3 rd elements.

3, 5, 10, 15, 12

As here 12 is smaller than only 15 hence the swapping will occurs between 15 and 12

3, 5, 10, 12, 15

Pseudo-code:

int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;
         while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;

    }