Bubble sort algorithm in Java

Question

I have written this code which basically sorts the array using bubble sort, however, I feel it is not very readable. Please let me know me how I can improve this code.

public class BubbleSort {

    public static void main(String[] args) {

        int arr[] = new int[] { 4, 1, 8, 5, 2, 0, 4, 3, 7, 9 };

        for (int i : arr) {
            System.out.print(i + " ");
        }

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

            }

        }
        System.out.println();
        System.out.println("Sorted array");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

}

Answer 1

Your code looks mostly good to me.

One thing: Functions can help increase readability of your code, and reduce the amount of duplicate code. Additionally, they make testing and (re-)using your code easier. Your main method should only be an entry point, it shouldn't really contain any logic itself.

Your main method might look like this:

public static void main(String[] args) {
    int[] array = new int[] { 4, 1, 8, 5, 2, 0, 4, 3, 7, 9 };

    printArray(array);
    int[] sortedArray = sortArray(array);
    printArray(sortedArray);      
}

Then just create those functions.

Misc

• You have some unnecessary newlines after }.
• temp could be renamed swap, making it more obvious what is happening.
• arr could be named array (arr may be fine in this context, but generally, you do not want to shorten your variable names, as it is less readable).

Answer 2

A bubble sort goes through every element every time. It looks like this:

while(true) {
    boolean done = true;
    for(int j = 0; j < arr.length - 1; j++) {
        if(arr[j] > arr[j+1]) {
            done = false;  // Do another pass
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
    if(done) { // No swaps? We're done.
        break;
    }
}

What you've actually implemented is an unoptimized reverse selection sort; in this case, you've combined a bubble sort with a selection sort, which has better performance than a pure bubble sort but not as efficient as a pure selection sort, primarily because you're making potentially far more swaps than you would with a pure selection sort.

You could change it from the current implementation to a pure selection sort with minimal change:

for (int i = 0; i < arr.length - 1; i++) {
    int min = i;
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[min]) {
            min = j;
        }
    }
    if(min != i) {
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

Answer 3

Since you're implementing bubble sort, I assume you're more concerned about clarity and readability than about performance (else you would've picked a different sorting algorithm). Starting from this viewpoint, my first recommendation would be to abstract out the swap into a helper method:

public class BubbleSort {

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {

        int arr[] = new int[] { 4, 1, 8, 5, 2, 0, 4, 3, 7, 9 };

        for (int i : arr) {
            System.out.print(i + " ");
        }

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }    
            }    
        }

        System.out.println();
        System.out.println("Sorted array");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

}

There, that's a lot clearer already, isn't it?

---

My next suggestion actually is a performance optimization: in bubble sort, after every pass, the elements located after the last swap must all be at their proper position already, and thus don't need to be examined any more. So you can rewrite your sorting loop like this:

int end = arr.length;  // anything at or above this point is already sorted
while (end > 1) {
    int lastSwap = 0;  // index of last swapped element  

    // walk the array, swap adjacent elements that are the wrong way around
    for (int i = 1; i < end; i++) {
        if (arr[i - 1] > arr[i]) {
            swap(arr, i - 1, i);
            lastSwap = i;
        }
    }

    end = lastSwap;    // all elements after last swap must be sorted
}

As a useful side effect, this optimization causes the outer loop to terminate as soon as the inner loop detects that the array is fully sorted.

Even with this optimization, the bubble sort will still perform poorly if there's a "turtle" element that takes a long time to sink to the beginning of the array. You could fix that by adding a second, reverse inner loop to quickly move such elements where they belong, turning you bubble sort into cocktail sort. Unlike the optimizations above, however, that would change the sequence of swaps performed by the algorithm, making it technically no longer a pure bubble sort. Still, let me show an example:

int start = 0, end = arr.length;  // range yet to be sorted
while (end - start > 1) {
    int lastSwap = 0;

    // upward sorting pass
    for (int i = start + 1; i < end; i++) {
        if (arr[i - 1] > arr[i]) {
            swap(arr, i - 1, i);
            lastSwap = i;
        }
    }
    end = lastSwap;

    // downward sorting pass
    for (int i = end - 1; i > start; i--) {
        if (arr[i - 1] > arr[i]) {
            swap(arr, i - 1, i);
            lastSwap = i;
        }
    }
    start = lastSwap;
}