6
\$\begingroup\$

I have created a simple implementation of the bubble sort algorithm. I have tried to make it as efficient as possible by following pseudocode which I have provided below, making some slight modifications to suit my needs.

The pseudocode:

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure

My code:

import java.util.Arrays;
import java.util.Scanner;
public class BubbleSortNumeric {
    public static void main (String [] args) {
        System.out.println("Enter a set of integers seperated by a space...");
        Integer [] unsortedData = getDataInput();
        Integer [] unsortedData2 = new Integer[unsortedData.length];
        System.arraycopy(unsortedData, 0, unsortedData2, 0, unsortedData.length);
        Integer [] sortedDataAscending;
        Integer [] sortedDataDescending;
        long start = System.nanoTime();
        sortedDataAscending = bubbleSortAscending(unsortedData);
        sortedDataDescending = bubbleSortDescending(unsortedData2);
        long stop = System.nanoTime();
        System.out.println("Ascending: " + Arrays.toString(sortedDataAscending));
        System.out.println("Descening: " + Arrays.toString(sortedDataDescending));
        System.out.println("Execution time: " + ((stop - start) / 1e+6) + "ms.");
    }

    private static Integer [] getDataInput() {
        Integer [] userInput = {};
        String strInput;
        try(Scanner sc = new Scanner(System.in)) {
            strInput = sc.nextLine();
        }
        String [] inputData = strInput.split("\\s+");
        try {
            userInput = Arrays.asList(inputData).stream().map(Integer::valueOf).toArray(Integer[]::new); 
        }catch(NumberFormatException e) {
            System.out.println("ERROR. Invalid input.\n" + e.getMessage());
        }
       return userInput;
    }

    private static Integer [] bubbleSortAscending(final Integer[] ascendingUnsorted) {
        int n = ascendingUnsorted.length;
        if(n == 1) {
            return ascendingUnsorted;
        }
        boolean swapped;
        int temp;
        do {
            swapped = false;
            for(int i = 1; i < n; i++) {
                if(ascendingUnsorted[i - 1] > ascendingUnsorted[i]) {
                    temp = ascendingUnsorted[i - 1];
                    ascendingUnsorted[i - 1] = ascendingUnsorted[i];
                    ascendingUnsorted[i] = temp;
                    swapped = true; 
                }
            }
            n--;
        }while(swapped == true);
        return ascendingUnsorted;
    }

    private static Integer [] bubbleSortDescending(final Integer [] descendingUnsorted) {
        int n = descendingUnsorted.length;
        if(n == 1) {
            return descendingUnsorted;
        }
        boolean swapped;
        int temp;
        do {
            swapped = false;
            for(int i = 1; i < n; i++) {
                if(descendingUnsorted[i - 1] < descendingUnsorted[i]) {
                    temp = descendingUnsorted[i];
                    descendingUnsorted[i] = descendingUnsorted[i - 1];
                    descendingUnsorted[i - 1] = temp;
                    swapped = true;
                }
            }
            n--;
        }while(swapped == true);
        return descendingUnsorted;
    }
}

Key things that I've tried to look into, and am currently unsure about:

  • Is using arrays the most efficeient way of storing this data to sort etc.?

  • Are there ways of making the code shorter, but keeping speed, by using things like Lambda expressions like I have done to convert the users input from a String [] to Integer []?

  • Overall, is it as efficient as this algorithm can be, or is there further improvements that can be made, without changing the core parts of the algorithm that makes it a bubble sort algorithm?

  • I have looked into using generic methods to allow the user to input and sort char data, but I was concerned about the effect this would have on performance, given that I'd be handling different data types etc.

\$\endgroup\$
  • 1
    \$\begingroup\$ More to the point, why are you trying to optimize bubble sort when there are plenty of better alternate algorithms to implement? \$\endgroup\$ – Patrick Roberts Sep 12 '15 at 20:57
  • 3
    \$\begingroup\$ @PatrickRoberts I am studying a decision maths module at school which is all about algorithms, and I thought, as a way to ensure I understand the algorithms, I should make an implementation of them in Java and try and make them as efficient as possible, I know there are better algorithms, but I am currenty studying bubble sort. I will be moving on and implementing better ones as I move on through the module! \$\endgroup\$ – James Sep 12 '15 at 21:00
5
\$\begingroup\$

Points On Your Existing Code

  1. unsortedData and unsortedData2 look weird to me. Try appending a 1 to unsortedData to make them line up.
  2. Arrays has a utility method called copyOf(array, length) that internally uses System.arraycopy(). It will save you a few lines.
  3. sortedAscendingData or ascendingSortedData makes more sense than sortedDataAscending. Same for sortedDataDescending. This is because [adjective(s)][noun] is more natural than [adjective(s)][noun][more adjectives]
  4. swapped == true is redundant. The while (or if, and so on) construct needs a boolean only. Therefore, you can shorten your swapped == true to simply swapped and (for example) swapped == false to !swapped.
  5. If you are using Scanner, then stick to it. Scanner is always preferred over String.split().
  6. You should declare variables close to where you need them (or in the smallest scope possible). int temp = array[i]; will do you no harm.
  7. Try to keep typos (i.e. typographical errors) like seperated and Descening to a minimum.
  8. If you really want performance, why are you using Integer? You should be using int. There is a special mapToInt method to deal with ints. Carrying around an array of Integers is expensive in terms of memory and computational steps ( due boxing and unboxing).
  9. If you really want to use Integer, generalise your code by using Number instead. You can directly call the compareTo() method which is implemented in all classes like Long, Double, BigInteger, etc. It helps reduce code redundancy, but it doesn't avoid the extra boxing/unboxing. This is an example of a readability/performance trade-off.
  10. Comparator is a useful class that helps you compare the Comparable implementations in your way. Since you want performance I won't discuss it here any further. But it would be better if you take a look at it anyway.
  11. One final point on final: This keyword is used to signify that the concerned variable is now effectively a constant, i.e. its value (including its contents) cannot change. Therefore, it makes no sense to add it before the arguments in the sorting methods, as you are changing them (internally).

The Refactored Code

Here is my version of the code, using ints and ensures better performance due to absence of overheads. See how I ditched split()? I haven't written this from scratch. I just took your code and fixed the parts that needed fixing. I left the others intact.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class BubbleSortNumeric {
    public static void main(String[] args) {
        System.out.println("Enter a set of integers separated by white space.");
        int[] unsortedData1 = getInts();
        int[] unsortedData2 = Arrays.copyOf(unsortedData1, unsortedData1.length);
        long start = System.nanoTime();
        int[] sortedAscendingData = bubbleSortAscending(unsortedData1);
        int[] sortedDescendingData = bubbleSortDescending(unsortedData2);
        long stop = System.nanoTime();
        System.out.println("Ascending: " + Arrays.toString(sortedAscendingData));
        System.out.println("Descending: " + Arrays.toString(sortedDescendingData));
        System.out.println("Execution time: " + ((stop - start) / 1e+6) + "ms.");
    }

    private static int[] getInts() {
        int[] userInput = {};
        List<String> strings = new ArrayList<>();
        try (Scanner sc = new Scanner(System.in)) {
            while (sc.hasNext()) {
                strings.add(sc.next());
            }
        }
        try {
            userInput = strings
                    .stream()
                    .mapToInt(Integer::parseInt)
                    .toArray();
        } catch (NumberFormatException e) {
            System.out.println("ERROR. Invalid input.\n" + e.getMessage());
        }
        return userInput;
    }

    private static int[] bubbleSortAscending(int[] array) {
        int n = array.length;
        if (n == 1) {
            return array;
        }
        boolean swapped;
        do {
            swapped = false;
            for (int i = 1; i < n; i++) {
                if (array[i - 1] > array[i]) {
                    int temp = array[i - 1];
                    array[i - 1] = array[i];
                    array[i] = temp;
                    swapped = true;
                }
            }
            n--;
        } while (swapped);
        return array;
    }

    private static int[] bubbleSortDescending(int[] array) {
        int n = array.length;
        if (n == 1) {
            return array;
        }
        boolean swapped;
        do {
            swapped = false;
            for (int i = 1; i < n; i++) {
                if (array[i - 1] < array[i]) {
                    int temp = array[i];
                    array[i] = array[i - 1];
                    array[i - 1] = temp;
                    swapped = true;
                }
            }
            n--;
        } while (swapped);
        return array;
    }
}

The reason this version runs faster (verify it) is because it avoids the unnecessary headache of boxing/unboxing. By the way, it was a nice idea to add the pseudocode. I'm looking forward to review more such implementations.

\$\endgroup\$
  • \$\begingroup\$ I have actually just tried running your version of the code against mine, and have found that yours gets stuck after you input a set of numbers, it isn't stuck in a loop, it is just waiting for more input (I think), and doesn't move on...? \$\endgroup\$ – James Sep 13 '15 at 12:59
  • \$\begingroup\$ Hmm. I used file redirection. In the console, there is no end of stream per se. Try with some static values or add a custom functionality that terminates when user inputs 0 or something. \$\endgroup\$ – Hungry Blue Dev Sep 13 '15 at 13:37
3
\$\begingroup\$

bubbleSortAscending and bubbleSortDescending are copy-and-paste of the same code except for one character. That is a very bad idea. Not only it makes the code longer for no reason, but if you ever want to make a change to one of the functions, you need to remember to change both, or you will get in serious trouble.

You should define just one method bubbleSort which takes a second argument which is either an instance of the Comparable interface, or a lambda that does the same.

\$\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.