Optimizing Bubble Sort in Java

By looking at the “classical” Bubble sort there can be found that the original algorithm is so unoptimized.


Original Bubble sort in Java

Let’s take a look at the original Bubble sort in Java:

private static void bubbleSortOriginal(int[] array) {
    boolean swapped;
    do {
        swapped = false;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
                swapped = true;
            }
        }
    } while (swapped);
}

Internal (second) loop always goes to the end of the array. Is it mandatory? Of course, no.

Optimizing Bubble sort in Java by decreasing N

So, after each iteration of the main loop, we are sure that the end of the loop can be decreased for the next iteration (because the largest element is already at the end). That’s why we just make lookup over the array shorter:

private static void bubbleSortOptimizedDecreasingN(int[] array) {
    boolean swapped;
    int n = array.length - 1;
    do {
        swapped = false;
        for (int i = 0; i < n; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
                swapped = true;
            }
        }
        n = n - 1;
    } while (swapped);
}

Optimizing Bubble sort in Java by remembering N

If we know where the largest element moved on the previous iteration, that is the reason for remembering its position, right? And, the condition of the algorithm’s end will be the fact that the largest element has not been swapped.

private static void bubbleSortOptimizedRememberingN(int[] array) {
    int n = array.length - 1;
    do {
        final int newN = n;
        n = 0;
        for (int i = 0; i < newN; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
                n = i + 1;
            }
        }
    } while (n > 0);
}

Bubble Sort in Java

So, let’s write a shorter version of the optimized Bubble sort in Java:

private static void bubbleSort(int[] array) {
    for (int n = array.length - 1, newN = n; n > 0; newN = n) {
        n = 0;
        for (int i = 0; i < newN; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
                n = i + 1;
            }
        }
    }
}

How to test and compare time

For checking if our sorting algorithm sorts array correctly, let’s write a method for generating a random array. The array will contain items from 1 to N.

private static int[] generateRandomArray(int length) {
    int[] result = new int[length];
    for (int i = 0; i < length; i++) {
        result[i] = i + 1;
    }
    shuffle(result);
    return result;
}

private static void shuffle(int[] array) {
    if (array.length > 1) {
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            swap(array, i, random.nextInt(array.length));
        }
    }
}

private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

After generating this method, it is easy to check if the array is properly sorted or not:

private static void assertSorted(int[] array) {
    for (int i = 1; i <= array.length; i++) {
        if (array[i - 1] != i) {
            throw new AssertionError(String.format("Array is not sorted: a[%d] != %s", i - 1, i));
        }
    }
}

To compare the execution time of a sorting algorithm, we will use interface Sorter:

private interface Sorter {
    void sort(int[] array);
}

And the method for copying an original array, running sort algorithms, checking sorted array and measuring time:

private static long runSorter(int[] original, Sorter sorter) {
    final int[] toSort = Arrays.copyOf(original, original.length);

    final long startTime = System.currentTimeMillis();
    sorter.sort(toSort);
    final long endTime = System.currentTimeMillis();

    assertSorted(toSort);

    return endTime - startTime;
}

Full Java code example

import java.util.Arrays;
import java.util.Random;

/**
 * @author Denis Migol
 */
public class BubbleSortOptimized {
    private static int[] generateRandomArray(int length) {
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            result[i] = i + 1;
        }
        shuffle(result);
        return result;
    }

    private static void shuffle(int[] array) {
        if (array.length > 1) {
            Random random = new Random();
            for (int i = 0; i < array.length; i++) {
                swap(array, i, random.nextInt(array.length));
            }
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private static void bubbleSortOriginal(int[] array) {
        boolean swapped;
        do {
            swapped = false;
            for (int i = 0; i < array.length - 1; i++) {
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    swapped = true;
                }
            }
        } while (swapped);
    }

    private static void bubbleSortOptimizedDecreasingN(int[] array) {
        boolean swapped;
        int n = array.length - 1;
        do {
            swapped = false;
            for (int i = 0; i < n; i++) {
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    swapped = true;
                }
            }
            n = n - 1;
        } while (swapped);
    }

    private static void bubbleSortOptimizedRememberingN(int[] array) {
        int n = array.length - 1;
        do {
            final int newN = n;
            n = 0;
            for (int i = 0; i < newN; i++) {
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    n = i + 1;
                }
            }
        } while (n > 0);
    }

    private static void bubbleSort(int[] array) {
        for (int n = array.length - 1, newN = n; n > 0; newN = n) {
            n = 0;
            for (int i = 0; i < newN; i++) {
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    n = i + 1;
                }
            }
        }
    }

    private static long runSorter(int[] original, Sorter sorter) {
        final int[] toSort = Arrays.copyOf(original, original.length);

        final long startTime = System.currentTimeMillis();
        sorter.sort(toSort);
        final long endTime = System.currentTimeMillis();

        assertSorted(toSort);

        return endTime - startTime;
    }

    private static void assertSorted(int[] array) {
        for (int i = 1; i <= array.length; i++) {
            if (array[i - 1] != i) {
                throw new AssertionError(String.format("Array is not sorted: a[%d] != %s", i - 1, i));
            }
        }
    }

    public static void main(String[] args) {
        final int[] randomArray = generateRandomArray(10000);

        System.out.println("Bubble sort 'classical-original algorithm' time: " + runSorter(randomArray, new Sorter() {
            @Override
            public void sort(int[] array) {
                bubbleSortOriginal(array);
            }
        }));

        System.out.println("Bubble sort optimized 'by decreasing N' time: " + runSorter(randomArray, new Sorter() {
            @Override
            public void sort(int[] array) {
                bubbleSortOptimizedDecreasingN(array);
            }
        }));

        System.out.println("Bubble sort optimized 'by remembering N' time: " + runSorter(randomArray, new Sorter() {
            @Override
            public void sort(int[] array) {
                bubbleSortOptimizedRememberingN(array);
            }
        }));

        System.out.println("Bubble sort rewritten 'by remembering N' time: " + runSorter(randomArray, new Sorter() {
            @Override
            public void sort(int[] array) {
                bubbleSort(array);
            }
        }));
    }

    private interface Sorter {
        void sort(int[] array);
    }
}

Output

10.000 items:

Bubble sort 'classical-original algorithm' time: 491
Bubble sort optimized 'by decreasing N' time: 295
Bubble sort optimized 'by remembering N' time: 255
Bubble sort rewritten 'by remembering N' time: 246

100.000 items:

Bubble sort 'classical-original algorithm' time: 27885
Bubble sort optimized 'by decreasing N' time: 22153
Bubble sort optimized 'by remembering N' time: 20657
Bubble sort rewritten 'by remembering N' time: 20469

Results

As we can see, optimizing Bubble sort is an easy (and a bit tricky) task and it can save execution time.