Question

1. Consider the following pseudocode for insertion-sort algorithm. The algorithm sorts an arbitrary array A[0..n − 1] of n elements.

void ISORT (dtype A[ ], int n) { int i, j; for i = 1 to n – 1 {     //Insert A[i] into the sorted part A[0..i – 1]     j = i;     while (j > 0 and A[j] < A[j – 1]) {         SWAP (A[j], A[j – 1]);         j = j – 1 }     } }

1. Illustrate the algorithm on the following array by showing each comparison/swap operation. What is the total number of comparisons made for this worst-case data?

A = (5, 4, 3, 2, 1)

2. Write a recursive version of this algorithm.

3. Let f(n) be the worst-case number of key comparisons made by this algorithm to sort n elements. Write a recurrence equation for f(n). (Note that the sequence of comparisons are exactly the same for both non-recursive and recursive versions. But, you may find it more convenienet to write the recurrence for the recursive version.)

4. Find the solution for f(n) by repeated substitution.

2. Consider the bubble-sort algorithm described below.

void bubble (dtype A[ ], int n) { int i, j; for (i = n − 1; i > 0; i − −)        //Bubble max of A[0..i] down to A[i].     for (j = 0; j < i; j + +)         if (A[j] > A[j + 1]) SWAP(A[j], A[j + 1]); }

1. Analyze the time complexity, T(n), of the bubble-sort algorithm.

2. Rewrite the algorithm using recursion.

3. Let f(n) be the worst-case number of key-comparisons used by this algorithm to sort n elements. Write a recurrence for f(n). Solve the recurrence by repeated substitution (i.e, iteration method).

Answer 1

Hey there!!

a) For this part observe that insertion sorts swap an element from its current position to its sorted position only by swiping it with its immediate neighbor that means for the worst case in which the first element is at the first position and has to be moved to the last position, it will take n-1 comparison now the second element has to be placed second to the last place then it will take n-2 comparisons where n is the size of the array for the third element it would be n-3 than n-4 and so on.

As a result the total number of comparisons would be comp=(n-1)+n-2+(n-3)+.......+(n-n-1)

comp={n(n-1)}/2b)

b)

if n <= 1 
    return; 
insertionSort(arr, n) 

    insertionSort(arr, n-1) 

j = n-2;

while j >= 0 and A[j] > A[n-1]{

    A[j+1]=A[j];

    j = j – 1;
}
A[j+1]=A[n-1];

  

This is the recursive algorithms it calls for til size n-1 until the array size has become 1 then it starts inserting the element to its sorted location after that the function ends and now the function call for array size=2 is called from the stack. The array it receives is an array of size 1 sorted. It then sorts the array of size =2 and function ends . Again the function call of size 3 gets a sorted array of size 2 it sorts this array and then passes it to the function call of array size 4. The sorting part works exactly like a normal insertion sort.

c) The recurrence relation would be T(n) =T(n-1)+O(n)

d)We know that T(1)=T(0)+1=1

then T(2)=T(1)+2=1+2=3

T(3)=T(2)+3=1+2+3=6.......

observing the pattern T(n)=1+2+3+4.....n=(n(n-1))/2 = (n²-n)/2 in terms of Big-Oh notation it would be T(n)=O(n²)

Ans-2 a). For every element, bubble sort does n-1 comparisons. In Big-Oh notation, bubble sort performs O(n)O(n) comparisons. Now for n element, the complexity for each individual element would be O(n) so to sort the whole array the complexity would be no.of elements *complexity to sort each element which gives us O(n²) complexity.

b)

bubbleSort(arr[], n)
{

    for (int i=0; i<n-1; i++)
        if (arr[i] > arr[i+1])
            swap(arr[i], arr[i+1]);

    bubbleSort(arr, n-1);;
} 

After the first call, the greatest element is moved to the last place then we call for n-1 size in which the second greatest element is moved to the second last place then we call for size n-3,n-4, and so on.

c)The recursive relation for bubble sort is the same as insertion sort and it would be solved the same way.

If there is any doubt about the answer please put it in the comments I will get back to you asap.

Please upvote if you like the answer .

Thanks for asking!!