Programming Tutorials and Interview Questions

- Implement Bubble Sort Algorithm in Java
- Java Program for Bubble Sort
- Pros and Cons of Bubble Sort
- Analysis of Bubble Sort
- References

Before implementing Java program for bubble sort let's first see how bubble sort functions to sort array elements in either ascending or descending order. *Bubble sort* is the simplest sorting algorithm among available ones. However, its simplicity does not carry much value because it is one of the most time consuming sorting algorithms, but as it's conceptually the simplest of the sorting algorithms and for that reason is a good beginning for exploration of sorting techniques. Here this algorithm is included just for beginners. Because of its poor *O(n ^{2})* runtime performance, it is not used often for large (or even medium-sized) lists. This article implements

Writing Java code for bubble sort is a trivial task. Let's assume that we have an array of length `N`

having randomly ordered elements indexed from `0`

to `N-1`

, and we want to sort it in ascending order. While sorting the array elements, bubble sort at one time can see only two adjacent elements of the array. Bubble sort starts from the left end of the array and compare two elements in position 0 and 1. If the element positioned at 0^{th} index is larger, we swap them. If the 1^{st} element is larger, we don't do anything. Then we move over one position and compare the elements in positions 1 and 2. Again, if the one on the left is larger, we swap them else do nothing. While doing so we place the largest element at the last position of the array. We repeat this process `N`

number of times so as to sort all array elements.

The following Java program develops a class `BubbleSort`

that contains a parameterized static generic method `bubbleSort`

for any base type `T`

. Note that Java provides the `java.util.Comparable`

interface that contains a single method, `compareTo`

. Any class that correctly implements this interface guarantees a total ordering of its instances.

class BubbleSort { public static <T extends Comparable<T>> void bubbleSort (T[] list, int size) { int swapOccurred = 1, outCounter, inCounter; T temp; // swapOccurred helps to stop iterating if the array gets sorted before // outCounter reaches to size for (outCounter = size - 1; outCounter > 0 && swapOccurred == 1; outCounter--) { swapOccurred = 0; for (inCounter = 0; inCounter < outCounter; inCounter++) { if (list[inCounter].compareTo(list[inCounter+1]) > 0) { temp = list[inCounter]; list[inCounter] = list[inCounter+1]; list[inCounter+1] = temp; swapOccurred = 1; } } } } } public class BubbleSortDemo { public static void main (String[] args) { Integer arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; BubbleSort.bubbleSort(arr, arr.length); System.out.println("Sorted Array: "); for(Integer i : arr) { System.out.println(i); } } } OUTPUT ====== Sorted Array: 1 2 3 4 5 6 7 8 9 10

The idea of above implementation is to put the smallest element at the beginning of the array (index 0) and the largest item at the end (index size-1). The loop counter `outCounter`

in the outer `for`

loop starts at the end of the array, at `size-1`

, and decrements itself each time through the loop. The items at indices greater than `outCounter`

are always completely sorted. The `outCounter`

variable moves left after each pass by `inCounter`

so that items that are already sorted are no longer involved in the algorithm.

The inner loop counter `inCounter`

starts at the beginning of the array and increments itself each cycle of the inner loop, exiting when it reaches out. Within the inner loop, the two array cells pointed to by `inCounter`

and `inCounter+1`

are compared, and swapped if the one in `inCounter`

is larger than the one in `inCounter+1`

.

Above implementation of `BubbleSort`

iterates through the array elements *O(N ^{2})* times in the worst case when the array to be sorted is reversely ordered. To make

`BubbleSort`

implementation somewhat efficient we added a flag `swapOccurred`

that tells us if a swap occurred or not. There will not even a single swap occur if the array is sorted, and in that case we can stop iterating through array elements.
*Bubble sort*, as such serves no benefit from the efficiency's point of view. Yet, it is taught in computer science courses, just for exploration of sorting techniques.

*Bubble sort* is very slow and runs in *O(N ^{2})* time in the worst case. However, after having

`swapOccurred`

introduced it shows some performance gains.
In this tutorial we discussed *Bubble sort*. We implemented bubble sort algorithm in Java. Bubble sort is the most basic and the slowest sorting technique though. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

The BBCâ€™s technology correspondent Rory Cellan-Jones gets a beer poured for him by a robotic barman - but how long does it take?

US politicians have voted to let ISPs gather and sell data about what Americans do online.

Customers who suffer poor service could get automatic payouts under Ofcom's plan.