Question

5. Write a recursive Bubble Sort algorithm that takes an array A of n numbers as input. Analyze its time complexity using a recursion tree. Implement your algorithm in Java

Answer 1

n : array length

public void bubbleSort(int A[], int n)

    {

        // Base case

        if (n == 1) return;   

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

        for (int i=0; i < n-1; i++){

            if (A[i] > A[i+1])

            {

                int temp = A[i];

                A[i] = arr[i+1];

                A[i+1] = temp;

            }

       }

        // Largest element is fixed, recur for remaining array

        bubbleSort(A, n-1);

    }

Time Complexity : O(n*n)