Our website is made possible by displaying online advertisements to our visitors. Please consider supporting us by disabling your ad blocker.

Previously you saw an implementation of Quicksort, one of the better sorting algorithms. This time weâ€™re going to look at a much inferior sorting algorithm which generally makes its appearance in introduction to computer science type courses. Iâ€™m talking about the Bubble Sort algorithm.

Bubble Sort via Wikipedia:

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.

The Bubble Sort algorithm is sub-par because of the outrageous time-complexity that it has for all sorting calls and weâ€™re going to see why.

```
public class Sorting {
public void bubbleSort(int[] unsorted) {
for(int i = 0; i < unsorted.length; i++) {
for(int j = 0; j < unsorted.length; j++) {
if(unsorted[i] < unsorted[j]) {
int temp = unsorted[i];
unsorted[i] = unsorted[j];
unsorted[j] = temp;
}
}
}
}
}
```

In the above code notice that our Bubble Sort implementation has two nested loops all iterating through the length of the array. For every array, sorted or not, the outer loop will iterate n times and the inner loop will iterate **n** times. This means that in every scenario our time-complexity will be **O(n^2)** which is terrible.

This implementation can be improved slightly to handle the scenario where the array is already sorted:

```
public class Sorting {
public void bubbleSort(int[] unsorted) {
boolean swapped = true;
while(swapped) {
swapped = false;
for(int i = 0; i < unsorted.length - 1; i++) {
if(unsorted[i] > unsorted[i + 1]) {
int temp = unsorted[i];
unsorted[i] = unsorted[i + 1];
unsorted[i + 1] = temp;
swapped = true;
}
}
}
}
}
```

Notice in the above code Iâ€™ve stripped out one of the for-loops replacing it with a while loop. This gives us slightly more control in the Bubble Sort algorithm. After entering the while loop we immediately assume the array is sorted so when the for-loop depletes, the algorithm stops, leaving us with a time-complexity of **O(n)**. If it was determined that the array was not sorted in the for-loop, then the full sort happens giving us a time-complexity of **O(n^2)**.

In case youâ€™re interested in testing the above code, you can create a driver class like follows:

```
public class MainDriver {
public static void main(String[] args) {
Sorting s = new Sorting();
int[] arr = new int[] {5, 3, 8, 9, 2, 1, 7, 10};
s.bubbleSort1(arr);
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
```

Then running the following from your Command Prompt or Terminal:

```
javac MainDriver.java
java MainDriver
```

Not much to it.

Although very simple to implement, the classic Bubble Sort algorithm is something that you probably should stay away from. If youâ€™re interviewing for a software engineering type position, you may be asked to sort an array. It is in your best interest to choose Quicksort or another algorithm that offers a better time. It is also a good idea to know why exactly one is better than the other.

If youâ€™ve ever been asked a question like this on an exam or in an interview, please share your experience in the comments.