Problem

So I have recently written a bubble sort in java and was wondering if the code is correct and if there was any way to make it even more efficient.

Here is my code:

```
void bubbleSort(int array[], int num){
if(num == 1)
return;
for(int i = 0; i < num - 1; i++){
if(array[i] > array[i+1]){
int num2 = array[i];
array[i] = array[i+1];
array[i+1] = num2;
}
}
}
```

Solution

The first question you should ask is why implement Bubble Sort in Java? Java has sorting built-in. So you could replace calls to your `bubbleSort(data, num)`

with `Arrays.sort(data, 0, num)`

to get a sorted array. Or if you just want to sort the whole thing, `Arrays.sort(data)`

. You can even take advantage of parallelism with `Arrays.parallelSort(data)`

.

The main reason to implement a Bubble Sort is that it can be built to verify that an array is already sorted and efficiently sort an almost sorted array. But your code does not do that. In fact, your code does not actually sort unless the data is almost sorted already.

Consider an input of `{ 4, 3, 2, 1 }`

. Your code will go through the following steps

```
{ 3, 4, 2, 1 }
{ 3, 2, 4, 1 }
{ 3, 2, 1, 4 }
```

Now the loop ends. You have successfully moved the `4`

into the correct position (and the `2`

happens to be in the right position). But the `3`

and `1`

are out of position. You’ve essentially done a quarter of the work. You would need to run that function twice more to finish the sort. And you’d generally run it a third time to verify that you are finished.

```
class BubbleSort {
public boolean bubble(int[] data, int top) {
boolean swapped = false;
for (int i = 1; i < top; i++) {
if (data[i - 1] > data[i]) {
int temp = data[i - 1];
data[i - 1] = data[i];
data[i] = temp;
swapped = true;
}
}
return swapped;
}
}
```

Prefer verb names for methods. I would call it `sort`

, except that this doesn’t sort. It just bubbles the largest item to the last position. So I simply call it `bubble`

.

I prefer names like `data`

to names like `array`

.

I removed your initial check. The `for`

loop will not run in that case, having the same effect. So you don’t need the initial check.

This version returns a `boolean`

to say whether the method did anything. How would we know that it was sorted? Then the data would be in order and we’d make no swaps. So this tracks whether it swapped or not. If it did not, it’s sorted. If it did swap, it’s not sorted.

I don’t check it, but `top`

has to be less than or equal to `data.length`

. If greater, you will get an array out of bounds exception (unless `top`

is `1`

and the array is empty, in which case it is sorted and will just return).

You could write a Bubble Sort using this method. Note that if you want to bubble the entire array, you don’t need `top`

. Just use `data.length`

. But there is a reason to have a separate `top`

if you’re calling this inside a Bubble Sort. Hint: note that the `4`

is in the correct position (last) after the first pass.