5
\$\begingroup\$

I have written this class which sorts the array using bubble sort. Please let me know how can I improve it. (I don't like recurrent code in if/else statement)

public class BubbleSort {

public static void numbers(int[] array){
    numbers(array, '<');
}

public static void numbers(int[] array, char direction){
    if(direction == '<'){
        for(int i = 0; i < array.length - 1; i++){
            for(int j = 0; j < array.length - i - 1; j++){

                if(array[j] < array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }
    else{
        for(int i = 0; i < array.length - 1; i++){
            for(int j = 0; j < array.length - i - 1; j++){

                if(array[j] > array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }
}

public static void letters(char[] array){
    letters(array, '<');
}

public static void letters(char[] array, char direction){
    if(direction == '<'){
        for(int i = 0; i < array.length - 1; i++){
            for(int j = 0; j < array.length - i - 1; j++){

                if(array[j] < array[j + 1]){
                    char tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }
    else{
        for(int i = 0; i < array.length - 1; i++){
            for(int j = 0; j < array.length - i - 1; j++){

                if(array[j] > array[j + 1]){
                    char tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }
}   
}
\$\endgroup\$
2
\$\begingroup\$

Bubble Sort has an inefficient worst case. In general, you could speed things up by switching from this \$O(n^2)\$ sort to one of the \$O(n \log n)\$ sorts, e.g. Quicksort. Simplest would be to just use Arrays.sort but perhaps this is a programming exercise (tagging as would let reviewers know that).

        for(int i = 0; i < array.length - 1; i++){
            for(int j = 0; j < array.length - i - 1; j++){

                if(array[j] < array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }

The one thing that Bubble Sort can do well is handle sorted input efficiently in \$O(n)\$ time. But you don't do that.

        for (int i = 0; i < array.length - 1; i++) {
            boolean bubbled = false;
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] < array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    bubbled = true;
                }
            }

            if (!bubbled) {
                return;
            }
        }

Now it will return after a single pass if the input is sorted. If the input is almost sorted, it may return on the second or third pass.

You can save a calculation an outer loop iteration if you're really trying to optimize.

        for (int i = array.length - 1; i > 0; i--) {
            boolean bubbled = false;
            for (int j = 0; j < i; j++) {
                if (array[j] < array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    bubbled = true;
                }
            }

            if (!bubbled) {
                return;
            }
        }

Now you don't have to calculate array.length - 1 - i on every outer iteration.

Note that a naive compiler might actually calculate that on each inner iteration in the original code.

\$\endgroup\$
0
\$\begingroup\$

You can remove the outer condition and put it into the inner loop. This will cause it to be calculated O(n^2) times instead of once, but you'll have one copy of your main code:
(edited! inner condition fixed)

    public static void numbers(int[] array, char direction){
        for(int i = 0; i < array.length - 1; i++){
            for(int j = 0; j < array.length - i - 1; j++){

                if(direction == '<' && array[j] < array[j + 1]
                   ||
                   direction == '>' && array[j] > array[j + 1]){
                        int tmp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = tmp;
                    }
                }
            }
        }
    }
\$\endgroup\$
  • \$\begingroup\$ This if condition isn't working because ((true && false) || true)(this condition is always true) and I don't think is good choice make code cleaner for slower algorithm. \$\endgroup\$ – GRO Jun 7 '16 at 15:57
  • \$\begingroup\$ @GRO Of course, you are right! I apology, should not have posted in a hurry. \$\endgroup\$ – CiaPan Jun 7 '16 at 16:13
  • \$\begingroup\$ Apologize. Still in hurry :-( \$\endgroup\$ – CiaPan Jun 7 '16 at 18:05
0
\$\begingroup\$

You could just sort in one direction, then check if required direction is the opposite. If yes, then reverse the existing array.

public static void numbers(int[] array, char direction){
    for(int i = 0; i < array.length - 1; i++){
        for(int j = 0; j < array.length - i - 1; j++){

            if(array[j] < array[j + 1]){
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }

    if(direction=='>'){
            var reverseArray=array.clone();
            Collections.reverse(Array.asList(reverseArray));
    }

    // Now you have your ascending order in 'array' and descending order in 'reverseArray'.
}
\$\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.