1
\$\begingroup\$

I have implemented simple BubbleSort algorithm. How can I optimize my code? Any suggestion would be helpful.

public class BubleSort {
    private int arr[];
    public static int COUNT;

public BubleSort(int array[]){
    this.arr = array;
}

public int[] getArray(){
    return this.arr;
}

public void setArray(int[] arr) {this.arr = arr;}

public BubleSort sortWithBuble(){
    if(getArray() == null){
        return null;
    }
    else {
        for(int j = 0; j < getArray().length;j++){
            for(int i = 0; i < getArray().length - 1; i++){
                if(getArray()[i] > getArray()[i+1]){
                    int temp = getArray()[i];
                    getArray()[i] = getArray()[i+1];
                    getArray()[i+1] = temp;
                    COUNT ++;
                }
            }
        }
    }
    return this;
}
}
\$\endgroup\$
  • \$\begingroup\$ Do you want to optimize the bubblesort itself, or do you want to optimize the process of sorting? If it's the latter, I could suggest other algorithms which offer more performance and aren't hard to implement. \$\endgroup\$ – Gabriel Aug 15 '16 at 2:58
  • \$\begingroup\$ You're calling getArray() way to often. Your class owns the arr field, simply use it. \$\endgroup\$ – D. Jurcau Aug 15 '16 at 10:01
2
\$\begingroup\$

Early return doesn't require an else

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

Since you return in the if, you don't need an else block.

Optimizing Bubble Sort

    for (int j = getArray().length - 1; j > 0; j--) {
        boolean swapped = false;

        for (int i = 0; i < j; i++) {
            if (getArray()[i] > getArray()[i+1]) {
                int temp = getArray()[i];
                getArray()[i] = getArray()[i+1];
                getArray()[i+1] = temp;
                COUNT++;
                swapped = true;
            }
        }

        if (! swapped) {
            return this;
        }
    }

This is the short circuit form of bubble sort. If you don't do any swaps on a given pass, the array is in order and you can return immediately. This gives it a best case of \$\mathcal{O}(n)\$.

Each iteration you effectively find the maximum value of that section of the array and move it to the end. As a result, you don't need to check the last value on the next pass. So you can decrease the last index checked each time.

It just so happens that that matches the number of iterations needed for the outer loop. So flip that around. Instead of incrementing up to it, decrement down. Now you can use the outer loop's index variable as the upper limit for the inner loop's index variable. As a result, it does about half the number of comparisons as previous. Same number of swaps though.

Optimizing Sort

Assuming that you aren't normally getting already sorted inputs, you could more simply sort with

    Arrays.sort(getArray());

That's a quick \$\mathcal{O}(n \log n)\$ sort, which is better than the expected case for Bubble Sort: \$\mathcal{O}(n^2)\$.

It's also less code.

Of course, you may be implementing a Bubble Sort for some reason other than efficient sorting.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.