Bubble Sort Implementation in Java

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

Implement Bubble Sort Algorithm in Java

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²) runtime performance, it is not used often for large (or even medium-sized) lists. This article implements bubble sort in Java and explains bubble sort algorithm briefly.

Java Program for Bubble Sort

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²) 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.

Pros and Cons of Bubble Sort

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.

Analysis of Bubble Sort

Bubble sort is very slow and runs in O(N²) time in the worst case. However, after having swapOccurred introduced it shows some performance gains.

Last Word

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!

References