A simple bubble sort implementation in Java

Question

I've written a Bubble Sort algorithm in Java and I want a review on these:

Performance improvements.
Code conventions.
Algorithm design improvements.
Cleaner approaches.

I would highly appreciate if you can review based on the points above, and I would prefer if you can add more points on top if it if you find necessary.

Here's the code:

package com.hassanalthaf.sortingalgorithms;

public class BubbleSort {

    private int temporary;

    public int[] sort(int[] numbers) {
        for (int mainIterations = 0; mainIterations < numbers.length; mainIterations++) {
            int comparisonsCount = (numbers.length - mainIterations) - 1;

            for (int comparisons = 1; comparisons < comparisonsCount; comparisons++) {
                if (numbers[comparisons] > numbers[comparisons + 1]) {
                    this.temporary = numbers[comparisons];
                    numbers[comparisons] = numbers[comparisons + 1];
                    numbers[comparisons + 1] = this.temporary;
                }
            }
        }

        return numbers;
    }

}

Here's my main class calling the BubbleSort sort method:

package com.hassanalthaf.sortingalgorithms;

public class Main {

    public static void main(String[] args) {
        int[] numbers = {1, 20, 51, 12, 43, 2, 20};

        BubbleSort bubbleSort = new BubbleSort();

        numbers = bubbleSort.sort(numbers);

        for (int iterations = 0; iterations < numbers.length; iterations++) {
            System.out.println(numbers[iterations]);
        }
    }

}

This produces an output:

All answers were equally useful. I ticked the one with most votes. — codez
– codez, Commented Jul 3, 2016 at 8:46

coderodde · Accepted Answer · 2016-06-25 14:20:53Z

2

Bug

On the array { 3, 1, 4, 5, 2 }, the result will be { 3, 1, 2, 4, 5 }. In order to fix this, in the inner for loop change

int comparisons = 1;

to

int comparisons = 0;

API

The Java coding conventions dictate that sorting routines are declared static, return nothing (have type void), and provide the version of the routine that can sort a particular subarray within an array.

Also, you might prefer to declare the constructor of BubbleSort as private, since that object does not do anything of interesting on its own.

Algorithm

Your algorithm runs always in \$\Theta(N^2)\$, whereas the actual bubble sort runs in \$\Theta(N)\$ on almost sorted input. Refer to the Wikipedia for pseudocode that is more adaptive.

Printing an integer array

Instead of

for (int iterations = 0; iterations < numbers.length; iterations++) {
    System.out.println(numbers[iterations]);
}

you can easily write

System.out.println(Arrays.toString(yourArray));

Hope that helps.

edited Jun 25, 2016 at 14:20

answered Jun 25, 2016 at 10:37

coderodde

32.3k15 gold badges79 silver badges205 bronze badges

\$\begingroup\$ I believe this algorithm is O(n^2) if you read the wikipedia. As far as I learnt, it is O(n^2) but can be optimized to O(log n) in some scenarios. \$\endgroup\$

codez
– codez

2016-06-25 20:51:28 +00:00
Commented Jun 25, 2016 at 20:51
\$\begingroup\$ @HassanAlthaf There is no sorting algorithm that may be "optimized" to \$\mathcal{O}(\log n)\$; best case is no better than \$\Omega(n)\$. \$\endgroup\$

coderodde
– coderodde

2016-06-26 12:07:31 +00:00
Commented Jun 26, 2016 at 12:07
\$\begingroup\$ If you look at wikipedia, there's an $O(log n)$ algorithm using repeat-until \$\endgroup\$

codez
– codez

2016-06-29 09:36:26 +00:00
Commented Jun 29, 2016 at 9:36
\$\begingroup\$ @HassanAlthaf Doing exactly what in \$\mathcal{O}(\log n)\$? \$\endgroup\$

coderodde
– coderodde

2016-06-29 09:39:53 +00:00
Commented Jun 29, 2016 at 9:39

Add a comment |

user14393 · Accepted Answer · 2016-06-25 09:07:38Z

I think the two biggest design problems are:

temporary, the temporary variable you use in sort, should be a local variable in the sort routine, not a member variable.
sort should be static.

There are times when it makes sense to have some sort of BubbleSortEngine class whose instances are objects that can perform a bubble sort. This is typically when the algorithm might need access to some precomputed data, or maybe to acquire resources that will be reused through several invocations of the algorithm, or hold configuration options, or is keeping track of performance metrics, or other such things. (but this pattern has its own advantages and disadvantages and there are other patterns that can be used to achieve that effect)

However, this implementation is very much not one of those times.

Making temporary a local variable will likely result in a performance increase. It would also allow multiple threads to safely invoke sort concurrently.

Similarly, making sort static will increase performance. Not directly, but because the current design will tempt an application to create new BubbleSort objects all the time whenever it needs to perform a sort.

Bobby · Accepted Answer · 2016-06-25 09:10:11Z

1

Javadoc

public class BubbleSort {
    private int temporary;
    public int[] sort(int[] numbers) {

There is no need that this is an instance class, a static utility class is very fitting for such tasks. Also, the temporary variable should be declared inside the function, not on a class scope.

for (int mainIterations = 0; mainIterations < numbers.length; mainIterations++) {

I like that you've used a full name instead of i, I like that. However, index would be more fitting and shorter.

this.temporary = numbers[comparisons];

this is unnecessary at this point.

public int[] sort(int[] numbers) {
    ...
    return numbers;

Your function takes an int array and returns an int array, this is very confusing. Without any further documentation a user would/could assume that you clone the given array and return a different one. Instead you modify the given one and return it. Which is cute if you try to create a "fluent" API but is here very confusing.

Either clone the given array and return that clone or do not return anything at all.

Otherwise this looks quite clean, nicely done.

answered Jun 25, 2016 at 9:10

Bobby

8,1662 gold badges35 silver badges43 bronze badges

\$\begingroup\$ What do you mean clone the given array? It will still return an int array. \$\endgroup\$

codez
– codez

2016-07-03 08:42:58 +00:00
Commented Jul 3, 2016 at 8:42
\$\begingroup\$ Yes, but it won't modify the original one. int[] toSort = new int[numbers.length]; System.arrayCopy(numbers, toSort, 0); or some such. \$\endgroup\$

Bobby
– Bobby

2016-07-04 16:47:15 +00:00
Commented Jul 4, 2016 at 16:47
\$\begingroup\$ Yes. I am aware. The array is passed by value, therefore, its a fresh new copy of the passed array. \$\endgroup\$

codez
– codez

2016-07-06 17:55:00 +00:00
Commented Jul 6, 2016 at 17:55
1

\$\begingroup\$ No, no, damn no. What you gave the impression that arrays are passed by value? They are passed by reference, like everything else, with the exception of primitive types. Arrays are not primitives. \$\endgroup\$

Bobby
– Bobby

2016-07-06 22:16:39 +00:00
Commented Jul 6, 2016 at 22:16
\$\begingroup\$ Oh @Bobby I see. My bad. \$\endgroup\$

codez
– codez

2016-07-07 15:16:08 +00:00
Commented Jul 7, 2016 at 15:16

Add a comment |

Stack Exchange Network

A simple bubble sort implementation in Java

3 Answers 3

You must log in to answer this question.

Hot Network Questions

A simple bubble sort implementation in Java

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions