Optimized Bubble Sort

Question

I would like to know how else I can optimize bubble sort so that it overlooks elements that have already been sorted, even after the first pass.

Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**]

We observe that [4,5,6] are already in sorted order, how can I modify my code so that it overlooks this 3 elements in the next pass? Which means the sort would be more efficient? Do you suggest a recursive method?

public static void bubbleSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        boolean is_sorted = true;
        for (int j = 0; j < a.length; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                is_sorted = false;
            }
        }
        if (is_sorted) return;
    }
}

Solution 1

First of all, you have an out-of-bounds access:

for (int j = 0; j < a.length; j++) {
    if (a[j] > a[j + 1]) {

for j == a.length-1, so the loop condition should rather be j < a.length-1.

But, in Bubble sort, you know that after k passes, the largest k elements are sorted at the k last entries of the array, so the conventional Bubble sort uses

public static void bubbleSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        boolean is_sorted = true;
        // skip the already sorted largest elements
        for (int j = 0; j < a.length - i; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                is_sorted = false;
            }
        }
        if (is_sorted) return;
    }
}

Now, that would still do a lot of unnecessary iterations when the array has a long sorted tail of largest elements, say you have k,k-1,...,1 as the first k elements and k+1 to 100000000 in order after that. The standard Bubble sort will pass k times through (almost) the entire array.

But if you remember where you made your last swap, you know that after that index, there are the largest elements in order, so

public static void bubbleSort(int[] a) {
    int lastSwap = a.length - 1;
    for (int i = 1; i < a.length; i++) {
        boolean is_sorted = true;
        int currentSwap = -1;
        for (int j = 0; j < lastSwap; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                is_sorted = false;
                currentSwap = j;
            }
        }
        if (is_sorted) return;
        lastSwap = currentSwap;
    }
}

would sort the above example with only one pass through the entire array, and the remaining passes only through a (short) prefix.

Of course, in general, that won't buy you much, but then optimising a Bubble sort is a rather futile exercise anyway.

Solution 2

public static Integer[] optimizedBubbleSort(Integer[] input) {
    long startTime = System.nanoTime();
    boolean swapped = true;
    for (int pass = input.length - 1; pass >= 0 && swapped; pass--) {
        swapped = false;
        for (int i = 0; i < pass; i++) {
            if (input[i] > input[i + 1]) {
                int temp = input[i];
                input[i] = input[i + 1];
                input[i + 1] = temp;
                swapped = true;
            }
        }
    }
    System.out.println("Time taken for OPTIMIZED bubbleSort: "
            + (System.nanoTime() - startTime));
    return input;
}

Solution 3

public static void BubbleSorter(params int[] input) {
    int newSize = input.Length - 1, size = 0;
    bool swap;
    do {
        swap = false;
        for (int j = 0; j < newSize; j++) {
            if (input[j] > input[j + 1]) {
                int temp = input[j + 1];
                input[j + 1] = input[j];
                input[j] = temp;
                swap = true;
                size = j;
            }
        }
        newSize = size;
    } while (swap);
    DisplayArrayElements(input);
}

Solution 4

you should use a variable "size" for the inner loop and change it to the latest swapped element in each cycle.This way your inner loop goes up to the latest "swapped" element and passes the rest that are unswapped (aka in their correctplace). i.e

do {
    int newsize = 0;
    for (int i = 1; i < size; i++) {
        if (a[i - 1] > a[i]) {
            int temp;
            temp = a[i - 1];
            a[i - 1] = a[i];
            a[i] = temp;
            newsize = i;
        }
    }
    size = newsize;
} while (size > 0);

View more solutions

Comments

[kent]

appreciate your detailed explanation as well as spotting that jarring error of mine!

[employee-0]

it is a bit cleaner/more clear to use a while loop for the outer loop and check the currentSwap variable.

[kbluue]

This is not optimized. You are only going in reverse and showing the time taken for the operation.

[Mindaugas Bernatavičius]

I did not know the last optimization for the long ordered tail, thanks.

[j__carlson]

This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review

[Raghavendra]

This won't sort completly