Question

Write a function to sort an array of integers and also determine and explain the worst
case complexity (Big O notation) of your algorithm. (You may NOT use Collections.sort)

Answer 1

CODE

void bubbleSort(int arr[])

    {

        int n = arr.length;

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

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

                if (arr[j] > arr[j+1])

                {

                    // swap arr[j+1] and arr[i]

                    int temp = arr[j];

                    arr[j] = arr[j+1];

                    arr[j+1] = temp;

                }

    }

Worst case occurs when array is reverse sorted. This is because in case, every pair of elements need to be swapped at each iteration making the time complexity O(n^2),