Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Optimized Bubble Sort

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;
    }
}
like image 393
kent Avatar asked Apr 24 '13 14:04

kent


People also ask

Why is bubble sort not optimized?

It is the slowest algorithm and it runs with a time complexity of O(n^2). Bubble sort can be optimized by using a flag variable that exits the loop once swapping is done. The best complexity of a bubble sort can be O(n). O(n) is only possible if the array is sorted.

How can you increase the efficiency of a bubble sort?

A better version of bubble sort, known as modified bubble sort, includes a flag that is set if an exchange is made after an entire pass over the array. If no exchange is made, then it should be clear that the array is already in order because no two elements need to be switched. In that case, the sort should end.

What is the time complexity of optimized bubble sort?

As a result, the time complexity of bubble sort in the best-case scenario is O(n).


1 Answers

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.

like image 179
Daniel Fischer Avatar answered Oct 15 '22 02:10

Daniel Fischer