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:

1
2
12
20
20
43
51

• codez: All answers were equally useful. I ticked the one with most votes.

Answer 1

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.

• codez: 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.
• coderodde: @HassanAlthaf There is no sorting algorithm that may be "optimized" to \$\mathcal{O}(\log n)\$; best case is no better than \$\Omega(n)\$.
• codez: If you look at wikipedia, there's an $O(log n)$ algorithm using repeat-until
• coderodde: @HassanAlthaf Doing exactly what in \$\mathcal{O}(\log n)\$?

Answer 2

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.

Answer 3

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.

• codez: What do you mean clone the given array? It will still return an int array.
• Bobby: Yes, but it won't modify the original one. int[] toSort = new int[numbers.length]; System.arrayCopy(numbers, toSort, 0); or some such.
• codez: Yes. I am aware. The array is passed by value, therefore, its a fresh new copy of the passed array.
• Bobby: 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.
• codez: Oh @Bobby I see. My bad.