Java Program to Implement Bubble Sort algorithm

Introduction

Bubble sort is one of the simplest sorting algorithms that works by repeatedly stepping through the list, comparing each pair of adjacent items and swapping them if they are in the wrong order. This process is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list.

In this article, you will learn how to implement the Bubble Sort algorithm in Java through detailed examples. Explore how to sort both numbers and strings, understand how to optimize the bubble sort algorithm, and see how its performance can be analyzed.

Implementing Bubble Sort in Java

Basic Bubble Sort Algorithm

1. Define the Bubble Sort function that takes an array of integers as input.

2. Implement the nested loops necessary for the comparison and swapping of elements.

   java Copy

   public static void bubbleSort(int[] arr) {
       int n = arr.length;
       for (int i = 0; i < n-1; i++) {
           for (int j = 0; j < n-i-1; j++) {
               if (arr[j] > arr[j+1]) {
                   // swap arr[j+1] and arr[j]
                   int temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
               }
           }
       }
   }
   

   This code iterates over the array, comparing adjacent elements. If they are in the incorrect order, it swaps them. It continues this process, reducing the number of comparisons in each subsequent iteration by one.

Calling the Bubble Sort Function

1. Create an array of integers.

2. Call the bubbleSort function.

3. Print the sorted array.

   java Copy

   public static void main(String[] args) {
       int[] arr = {64, 34, 25, 12, 22, 11, 90};
       bubbleSort(arr);
       System.out.println("Sorted array");
       for (int i=0; i < arr.length; i++) {
           System.out.print(arr[i] + " ");
       }
   }
   

   Here, an unsorted array is defined and passed to the bubbleSort method. Once sorted, the array is printed out line by line.

Sorting Strings with Bubble Sort

1. Modify the Bubble Sort function to handle an array of Strings.

2. Use the compareTo method for comparing string elements.

   java Copy

   public static void bubbleSortStrings(String[] arr) {
       int n = arr.length;
       for(int i = 0; i < n-1; i++) {
           for(int j = 0; j < n-i-1; j++) {
               if(arr[j].compareTo(arr[j+1]) > 0) {
                   String temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
               }
           }
       }
   }
   

   The process remains similar to the integer sorting example, but instead of using the > operator, compareTo is used to determine the order of strings.

Optimizing Bubble Sort

1. Introduce a boolean flag to monitor whether elements are swapped in the inner loop.

2. Break out of the outer loop if no swaps are made in the inner loop, which indicates that the array is already sorted.

   java Copy

   public static void optimizedBubbleSort(int[] arr) {
       int n = arr.length;
       boolean swapped;
       for (int i = 0; i < n-1; i++) {
           swapped = false;
           for (int j = 0; j < n-i-1; j++) {
               if (arr[j] > arr[j+1]) {
                   int temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
                   swapped = true;
               }
           }
           if (!swapped) break;
       }
   }
   

   This optimized version reduces the number of iterations by stopping early if no more swaps are needed.

Conclusion

Implementing Bubble Sort in Java is a fundamental exercise that helps you understand basic sorting mechanisms. While not the most efficient for large datasets compared to more advanced algorithms like quicksort or mergesort, it offers a clear and straightforward approach ideal for educational purposes. Experiment with these implementations to deepen your understanding of sorting algorithms in Java—starting with simple structures before moving on to more complex ones ensures a solid foundation in algorithmic thinking.