Question

07-15 pts) Develop a recursive version of the Bubble Sort algorithm. (a) Write the pseudo code of the algorithm and justify that it is recursive and works correctly Write the recurrence relation for the algorithm and solve it using one of the two approaches discussed in class, as appropriate. Solve the recurrence relation and show that the time complexity of the recursive algorithm is θ(n).

Answer 1

Answer(a):

assuming sorting in increasing order-

Algorithm bubbleSort( arr[], n)

{

    // Base case: array with one element

    if (n == 1)

        return;

    // One pass of bubble sort. After this pass, the largest element is moved (or bubbled) to end.

//after each recursive call largest element of current array is bubbled to end

// at last one element will be left and all elements right to it will be sorted

    for ( i=0; i<n-1; i++) //runs n-1 times

        if (arr[i] > arr[i+1]) // if it's out of order then swap

            swap(arr[i], arr[i+1]);

    // Largest element is fixed,

    // recur for remaining array

    bubbleSort(arr, n-1);

}

Answer(2):

let's say bubbleSort algo takes T(n) time to sort n elements and T(1)=K (time to sort 1 element is constant)

then recurrence relation is:

T(n) = T(n-1) + C*(n-1) ---------------(1)

C is some constant; C*(n-1) is the time of FOR loop to bubble out largest element; T(n-1) is time to sort rem. n-1 elements.

substituting n by n-1 in eq(1):

T(n-1) = T(n-2) + C*(n-2) ----------------(2)

substituting n by n-2,n-3,n-4,....3,2 in eq(1)

T(n-2) = T(n-3) + C*(n-3) -----------------(3)

T(n-3) = T(n-4) + C*(n-4) -----------------(4)

........................................

T(2) = T(1) + C*(1) ----------------(n-1)

Adding eqns 1 through (n-1), we get:

T(n) = T(1) + C*(1+2+.....+(n-1))

T(n) = K + C*(n*(n-1)/2) = (C/2)*n² - (C/2)*n + K

i.e. T(n) is O(n²)

hence BubbleSort is O(n²).