# Optimized Bubble Sort (Java)

I would like to know how else I can optimize bubble sort so that it overlooks elements that have already been sorted, even after the first pass.

```Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**]
```

We observe that [4,5,6] are already in sorted order, how can modify my code so that it overlooks this 3 elements in the next pass? (which means the sort would be more efficient?) Do you suggest a recursive method?

```public static void bubblesort(int[] a) {
for(int i=1; i<a.length; i++) {
boolean is_sorted = true;

for(int j=0; j<a.length; j++) {
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
is_sorted = false;
}
}

if(is_sorted) return;
}
}
```

Thanks for your time!

## Answer

First of all, you have an out-of-bounds access:

```    for(int j=0; j<a.length; j++) {
if(a[j] > a[j+1]) {
```

for `j == a.length-1`, so the loop condition should rather be `j < a.length-1`.

But, in Bubble sort, you know that after `k` passes, the largest `k` elements are sorted at the `k` last entries of the array, so the conventional Bubble sort uses

```public static void bubblesort(int[] a) {
for(int i=1; i<a.length; i++) {
boolean is_sorted = true;

for(int j=0; j < a.length - i; j++) { // skip the already sorted largest elements
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
is_sorted = false;
}
}

if(is_sorted) return;
}
}
```

Now, that would still do a lot of unnecessary iterations when the array has a long sorted tail of largest elements, say you have `k,k-1,...,1` as the first `k` elements and `k+1` to `100000000` in order after that. The standard Bubble sort will pass `k` times through (almost) the entire array.

But if you remember where you made your last swap, you know that after that index, there are the largest elements in order, so

```public static void bubblesort(int[] a) {
int lastSwap = a.length-1;
for(int i=1; i<a.length; i++) {
boolean is_sorted = true;
int currentSwap = -1;

for(int j=0; j < lastSwap; j++) {
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
is_sorted = false;
currentSwap = j;
}
}

if(is_sorted) return;
lastSwap = currentSwap;
}
}
```

would sort the above example with only one pass through the entire array, and the remaining passes only through a (short) prefix.

Of course, in general, that won’t buy you much, but then optimising a Bubble sort is a rather futile exercise anyway.