In Detail : Bubble Sort In Java Along With Generics Implementation

Bubble Sort :

    Bubble Sort is an elementary sorting algorithm with O(n^2) worst case running time complexity. Bubble Sort is often taught to the novice programmers in introductory Computer Science courses.

How Bubble Sort Works?

    Bubble Sort consists of a simple double for loop. The first iteration of the inner for loop moves through the array / list from bottom to top i.e from index 0 to index n-1, comparing adjacent keys. If the index at 'i' is greater than the index at 'i+1', then the two values are swapped. Once the highest element encountered this process will cause it to "bubble' up to the top of the array. The second pass through the array repeats this process.

    How ever because we know that the highest value is reached to the top of the array on the 1st pass, there is no need to compare top two elements on the second pass. Like wise, each succeeding pass through the array compares adjacent elements, looking at one value less than the preceding pass.

Implementation Of Bubble Sort In Java :

private void bubbleSort(int[] inputArray) {

        int temp = 0; // initializing local varibale temp

        /*
         * The outer for loop has to execute exactly '1' less than 
         * the length of the input array.        
         */
        for(int j = 1; j < inputArray.length; j++) {

            /* in each pass we have to iterate through 1 less than

             * the number of elements compared in the previous pass

             */
            for(int i = 0; i < inputArray.length - j; i++) {
                if(inputArray[i] > inputArray[i+1]) {
                    temp = inputArray[i];
                    inputArray[i] = inputArray[i+1];
                    inputArray[i+1] = temp;
                }
            }

            /* printing elements in each iteration */
            System.out.print("iteration- " + j + " - ");
            for(int i : inputArray) {
                System.out.print(" " + i);
            }
            System.out.println();
        }
    }

Implementation of An Improved Version Of Bubble Sort :

    The simple implementation of Bubble Sort, the outer for loop executes exactly 'n-1' no of times, where n is the length of the input Array / List, irrespective of the input size. so, when ever we encounter an Array which is already sorted, We don't have to do all the comparisons.  In improved version of Bubble Sort, we can eliminate this case if all the elements are sorted from lower to higher.

private void bubbleSortI(int[] inputArray) {

        int temp = 0;
        boolean swapped = true; // local initialisation boolean variable
        /*
         * The outer for loop has to execute exactly '1' less than 
        * the length of the input array.        
         */
        for(int j = 1; j < inputArray.length && swapped; j++) {
            swapped = false;
            for(int i = 0; i < (inputArray.length -j); i++) {
                if(inputArray[i] > inputArray[i+1]) {
                    temp = inputArray[i];
                    inputArray[i] = inputArray[i+1];
                    inputArray[i+1] = temp;
                    swapped = true;
                }
            }
            System.out.print("iteration - " + j + " - ");
             for(int i : inputArray) {
                System.out.print(" " + i);
            }
            System.out.println();
        }        
   }

Implementation Of Bubble Sort That Supports Generic Array In Java :

    The two implementations of Bubble Sort works only for Integer input Array. In real time, we need to sort different types of Arrays. Below is the implementation that supports Generic Array in Java.

private <E extends Comparable<E>>void bubbleSortG(E[] inputArray) {

        E temp;

        boolean swapped = true;

        for(int j = 1; j < inputArray.length & swapped; j++) {

            swapped = false;

            for(int i = 0; i < inputArray.length - j; i++) {

                if(inputArray[i].compareTo(inputArray[i+1]) > 0) {

                    temp = inputArray[i];

                    inputArray[i] = inputArray[i+1];

                    inputArray[i+1] = temp;

                    swapped = true;

                }

            }

        }

        for(E i: inputArray) {

            System.out.print(" " + i);

        }

    }

When To Use Bubble Sort ?

    Because of O(n^2) time complexity, Bubble Sort is not used in real time.Some elementary sorting algorithms performs better than Bubble Sort even though they have same O(n^2) complexity for example Insertion Sort . However, as mentioned Bubble Sort is used for teaching in introductory computer science courses.

Properties Of Bubble Sort :

1. O(1) extra space in swapping.
2. O(n^2) time complexity in Best, Worst & Average case for simple Bubble Sort.
3. O(n) time complexity for Best case in case of improved Bubble Sort.


Measuring Time Complexity Of Bubble Sort : 

    In Bubble Sort, the outer for loop executes for n-1 times, where n is size of input. For every time, the inner for loop executes for one time less than its previous iteration. There for the time complexity is

(n-1) + (n-2) + (n-3) + .... + 1 = (n-1) (n) / 2 = (n^2 - n) / 2 = O(n^2) .

In the simple implementation, the no of iterations and comparisons are always same irrespective of the order and number of elements of input Array. So the above computed time complexity holds for Best, Worst & Average case.

For improved version of Bubble Sort, the best case running time is O(n). This occurs when all the elements are sorted already from lower to higher, in this case outer for loop executes for once, and inner for loop also executes for once and number of comparisons is (n-1), there fore time complexity in best case is O(n).