NEED ALL STEPS Thanks in advance We can express Insertsort a

NEED ALL STEPS. Thanks in advance!

We can express Insert-sort as a recursive procedure as follows. In order to sort A[l...n], we recursively sort A[l...n- 1] and then insert .A[n] into sorted array A[l...n-1] Write the pseudocode for this recursive version of Insert-sort, name it Insert-SORT-RECUR. Write a recurrence for the running time of of INSERT-SORT-RECUR. Find the solution of this recurrence relation. Is INSERT-SORT-RECUR more expensive than INSERT-SORT?

Solution

a)Below is the Insert Sort code:

public static int[] RecursiveInsertionSort(int[] array, int n) {
     int i;
     if (n > 1)
        RecursiveInsertionSort(array, n - 1);
     else {
        int k = array[n];
        i = n - 1;
        while (i >= 0 & & array[i] > k) {
            array[i + 1] = array[i];
            i = i - 1;
        }
        array[i + 1] = k;
    }
    return array;
}

b) For recurrence for the running time of an Insert sort we have,

T(n) = O(1) , if n=1

T(n) = T(n-1)+O(n) , if n>1

T(n1) - For recursively sorting the previous (n - 1) elements.

O(n)- Running time for choosing the appropriate position of the element in the sorted array.

T(n)=T(n1)+n

=n+(n1)+T(n2)

=n+(n1)+(n2)+T(n3)

=n+(n1)+(n2)+....+2+T(1)

=n(n-1)/2+O(1)

=O(n^2)

So, T(n)=O(n^2)

c) Simple insertion sort is good only for small n.

Balance sorting vs. merging: Merge equal size chunks.

How to merge:

i=1, j=1

for k=1 to 2n

if A(i)<B(j)

then

C(k)=A(i)

i++

else

C(k)= B(j)

j++

end

O(n) time !!

d) Basic idea: divide and conquer

» Divide into 2 (or more) subproblems.

» Solve each subproblem recursively.

» Combine the results.

Insertion sort is just a bad divide & conquer !

» Subproblems:

      (a) last element

      (b) all the rest

» Combine: find where to put the last element

Thank you.