In this post I would be discussing the implementation of bubble sort in Java. Bubble sort, is a simple sorting algorithm that works by repeatedly stepping through the array to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the array is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large arrays. It’s not very efficient for large arrays because elements move over short distances, that is, one at a time.

The main point is that in bubble sort adjacent elements are compared and then swapped(interchanged) if necessary. For example, if we are going to sort an array in ascending order, we would swap (interchange) two adjacent elements if the first one is bigger than the next element.
Let’s say we want to sort the numbers 5,6,3,4,1 and 2. The process of comparing adjacent element and sorting would be as follows:

5 6 3 4 1 2 
5 6 3 4 1 2 Comparing 5 & 6 no change
5 3 6 4 1 2 Comparing 3 & 6 swapped
5 3 4 6 1 2 Comparing 4 & 6 swapped
5 3 4 1 6 2 Comparing 1 & 6 swapped
5 3 4 1 2 6 Comparing 2 & 6 swapped
3 5 4 1 2 6 Comparing 3 & 5 swapped
3 4 5 1 2 6 Comparing 4 & 5 swapped
3 4 1 5 2 6 Comparing 1 & 5 swapped
3 4 1 2 5 6 Comparing 2 & 5 swapped
3 4 1 2 5 6 Comparing 3 & 4 no change
3 1 4 2 5 6 Comparing 1 & 4 swapped
3 1 2 4 5 6 Comparing 2 & 4 swapped
1 3 2 4 5 6 Comparing 1 & 3 swapped
1 2 3 4 5 6 Comparing 2 & 3 swapped

Notice how the elements are moving to their places one place at a time. Also notice that arrays are being is sorted from right.

Students sometimes find the sorting techniques difficult because they try to learn it instead of understanding the underlying logic. Try to understand that if there is only one element, no comparison is required. If there are two elements, one comparison is required. Therefore, for an array a whose length is a.length, the array needs to be passed (traversed) a.length-1 times. Only adjacent elements are compared, that is, a[x] and a[x+1], given that ‘x’ is the control variable of the loop.

The java program for sorting an array in descending order using bubble sort would be as follows:

class BubbleSort{
    public static int[] bubbleSort( int a[] ){
        int temp;
        for(int i=0; i < a.length-1;i++){
            for(int x=0;x < a.length-i-1;x++){
                if(a[x+1] < a[x]){
                    temp=a[x];
                    a[x] = a[x+1];
                    a[x+1] = temp;
                }
            }
        }
        return a;
    }
    public static void display( int a[] ){
        for( int n: a ){
            System.out.print( n + " " );
        }
        System.out.println();
    }
    public static void main(String args[]){
        int a[]={5,6,3,4,1,2};
        a = bubbleSort( a );
        display( a );
    }
}

The outer loop at line number 4, is running from 0 to a.length-1 and is for comparing the number of passes as discussed above. The inner loop at line number 10, is running from 0 to a.length-1-i. In many books, the outer loop runs up to a.length-1 only. Please understand and notice from the above example that in bubble sort the elements reached their intended positions starting from the back. That is, the array get sorted starting from the rear. First the last element reaches it’s place, then the second last element reaches it’s place and so on. As we move forward with the sorting process array is sorted from the rear. To avoid comparing the elements which are already sorted (and wasting valuable time) each time we are limiting the extent of comparison by one by taking the loop up to a.length -1 -i. This increases efficiency.

The above code would give correct output in all cases but is not very efficient because it keeps on doing the comparisons even after the array is fully sorted. Let us understand this with the help of an example. Let us say, we want to sort an array which is almost sorted, like { 2, 1, 3, 4, 5, 6 }. In this case the array would be sorted as soon as the elements 1 and 2 are compared and sorted but the loops would keep on running till all the passes are complete and all the adjacent elements are compared! This can be easily avoided by introducing a boolean variable to check if any elements has been swapped or not. If no swapping occurs for the entire pass, we can conclude that the array is sorted and no more comparisons are needed. The Java program after incorporating the swapping variable for sorting an array in descending order using bubble sort would be as follows:

class BubbleSort{
    public static int[] bubbleSort( int a[] ){
        int temp;
        boolean swapped;
        for( int i=0; i < a.length-1;i++ ){
            swapped = false;
            for(int x=0; x < a.length - i - 1; x++ ){
                if( a[ x+1 ] < a[ x ] ){
                    temp=a[ x ];
                    a[ x ] = a[ x + 1 ];
                    a[ x + 1 ] = temp;
                    swapped = true;
                }
            }
            if( !swapped ) break;
        }
        return a;
    }
    public static void display( int a[] ){
        for( int n: a ){
            System.out.print( n + " " );
        }
        System.out.println();
    }
    public static void main(String args[]){
        int a[]={5,6,3,4,1,2};
        a = bubbleSort( a );
        display( a );
    }
}

The only change required in the above program to change the sort order from ascending to descending would be to change the < to > where we are comparing the adjacent elements. As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.