Bubble Sort implementation in Java

Question

I want to know if there is any other better way to write this algorithm. What other data structures could be used to make it more simple and effective?

public class BubbleSort {

        public static void bubbleSort(int array[]) {
            int n = array.length;
            int k;
            for (int m = n; m >= 0; m--) {
                for (int i = 0; i < n - 1; i++) {
                    k = i + 1;
                    if (array[i] > array[k]) {
                        swapNumbers(i, k, array);
                    }
                }
                printNumbers(array);
            }
        }

        private static void swapNumbers(int i, int j, int[] array) {

            int temp;
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        private static void printNumbers(int[] input) {

            for (int i = 0; i < input.length; i++) {
                System.out.print(input[i] + ", ");
            }
            System.out.println("\n");
        }

        public static void main(String[] args) {
            int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
            bubbleSort(input);

        }
    }

Output:

    2, 4, 6, 9, 12, 23, 0, 1, 34, 
    2, 4, 6, 9, 12, 0, 1, 23, 34, 
    2, 4, 6, 9, 0, 1, 12, 23, 34, 
    2, 4, 6, 0, 1, 9, 12, 23, 34, 
    2, 4, 0, 1, 6, 9, 12, 23, 34, 
    2, 0, 1, 4, 6, 9, 12, 23, 34, 
    0, 1, 2, 4, 6, 9, 12, 23, 34, 
    0, 1, 2, 4, 6, 9, 12, 23, 34, 
    0, 1, 2, 4, 6, 9, 12, 23, 34, 
    0, 1, 2, 4, 6, 9, 12, 23, 34

Answer 1

Efficiency

• As someone else mentioned, the inner loop only needs to run up to m-1.
• The standard optimization is that if an entire inner loop runs without ever swapping, then the array is now sorted and you can quit early. Notice how it prints the same thing the last 4 times.

Style

• If you've done bullet point 1 above, the only usage of n will be for (int m = n..., so you can just replace that with its definition and get rid of int n = array.length; above.
• You don't need to declare 'int k;' at the top, Java is smart enough to make that optimization. You can just use int k = i + 1;.
• In swapNumbers, combine the first two lines into int temp = array[i];

Looking Forward

Right now, it's difficult to reuse bubbleSort because it spews output to the console. I get that you want to see what it's doing, but once it's working you should take that out. The sort function should only be responsible for sorting; the user of the function (in this case, the main method) can decide what to do with the results (e.g., print them).

If you want to be able to debug it in the future, then put it behind a debugging flag:

// this goes top-level in the BubbleSort class:
private static final boolean DEBUG = false;
// then, inside bubbleSort:
if (DEBUG)
    printNumbers(array);

Answer 2

I like it a lot. It's not exactly how I would do things, but overall the code is very readable.

Some things to think about:

1) Every variable creates a bit of extra cognitive load for the reader. MattPutnam mentions that you could eliminate n and just use array.length directly. I agree. For similar reasons, you might consider getting rid of k:

if (array[i] > array[k]) {

becomes

if (array[i] > array[i+1]) {

That in itself creates a different kind of cognitive load on the reader, but in my case I prefer it because I think of it as (value at named-address) compared (value at named-address's neighbor). It's subjective; I suggest you try it and decide for yourself.

2) swapNumbers is its own function right now, maybe it shouldn't be.

• You'd be trading 1 isolated line of code in the inner loop for 3 simple lines, while getting rid of an entire function.
• swapNumbers is a great semantic function name that suggests it encapsulates higher-level behavior, but the required arguments aren't necessarily intuitive. The integers are understood to be indexes, but the values in the array are also integers, so the intent isn't 100% clear without reading the implementation. Ultimately, it might be cleaner to just do the swap in-situ.

3) If you were more interested in a potential performance enhancement, instead of running the loop array.length-1 times (worst case), you could set a flag tracking whether or not a given iteration actually swapped anything--you'd exit after an iteration failed to swap anything. Works well in certain "almost-sorted" scenarios.

If you do this, your for loop with counter m becomes a while loop with flag.

4) printNumbers(array) doesn't belong in the actual sorting method. Totally a valid instinct for debugging/dev [or satisfying the requirements of an assignment :-) ]; otherwise make sure you remove that line after you're "done". Sorting an array shouldn't dump console-output as a side-effect.

Answer 3

Boundary conditions

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

What happens when m is zero? First iteration of the inner for loop, it checks if 0 < 0 - 1, which is always false. Instead say

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

That cuts off two iterations of the outer loop which were totally unnecessary (m = n and m = 0) because i will never be less than 0 or -1. It also avoids relying on the compiler to notice that n - 1 is invariant to the loop and optimize it out.

I also changed n to m in the inner loop as others suggested.

Early exit

Traditionally bubble sort has had a bad worst case (\$O(n^2)\$) but a good best case (\$O(n)\$). The best case occurs when the data is already sorted. Your algorithm does not have a best case shortcut. It always takes the same amount of time. In your example, it sorts a sorted list three times. Consider instead

            for (int m = array.length - 1; m > 0; m--) {
                boolean hasSwapped = false;
                for (int current = 0; current < m; current++) {
                    int next = current + 1;
                    if (array[current] > array[next]) {
                        swapNumbers(current, next, array);
                        hasSwapped = true;
                    }
                }

                if (! hasSwapped) {
                    return;
                }
            }

or

            boolean needsSorted = true;
            for (int m = array.length - 1; needsSorted && m > 0; m--) {
                needsSorted = false;
                for (int current = 0; current < m; current++) {
                    int next = current + 1;
                    if (array[current] > array[next]) {
                        swapNumbers(current, next, array);
                        needsSorted = true;
                    }
                }
            }

I find the first version easier to read, but perhaps the second version is easier to understand. Both do essentially the same thing.

I renamed i and k to more descriptive names. The name i wasn't too bad, but k made no sense. Once I changed k, it made sense to change i as well.

Average Case

Performance will depend on how sorted the data is. The average over all possible inputs is going to be close to the worst case. But you may find that the kind of inputs that you actually get might be better. Note that the Java standard sort is \$O(n \log n)\$ in the average case. Unless your bubble sort can do better, you'd probably be better off sticking with the standard sort.

Note: you may be doing this purely as an exercise. That's fine. I just wouldn't want people walking away from this thinking that there is generally a reason for people to implement their own sorts. There almost never is.

Answer 4

After the first outer loop has run once you know that the largest element is at the back of the array. This means that you can shrink the number of iterations of the inner loop by 1 each time the outer loop completes

public static void bubbleSort(int array[]) {
    int n = array.length;
    int k;
    for (int m = n; m > 0; m--) {
        for (int i = 0; i < m - 1; i++) { //<-- replace n with m
            k = i + 1;
            if (array[i] > array[k]) {
                swapNumbers(i, k, array);
            }
        }
        printNumbers(array);
    }
}

However there are better sorting algorithms (like quicksort) and there is a built-in sort in java.util.Arrays (and one in java.util.Collections that works on Lists) which has been used for a long time and can be assumed to be efficient enough for most applications.