Implementation of Bubble Sort Algorithm in Java

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, which indicates that the list is sorted. In this article, we’ll start with a basic version of the bubble sort algorithm in Java to sort a list of numbers in ascending order. We’ll then explore several variations, including sorting in descending order, optimizing the algorithm for better performance, and sorting custom objects.

Prerequisites:

Basic Bubble Sort Implementation

Let’s start with a standard version of bubble sort in Java. This version will sort a list of numbers from smallest to largest.

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    int n = arr.length; // Get the length of the array

    // Outer loop: Each pass "bubbles" the largest element to its correct position
    for (int i = 0; i < n - 1; i++) {
      // Inner loop: Compares adjacent elements and swaps them if needed
      for (int j = 0; j < n - i - 1; j++) {
        // Compare adjacent elements
        if (arr[j] > arr[j + 1]) {
          // Swap arr[j] and arr[j+1]
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }

  // Utility method to print array
  public static void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    System.out.println("Original array:");
    printArray(arr);

    bubbleSort(arr); // Call bubble sort method

    System.out.println("Sorted array:");
    printArray(arr);
  }
}

Explanation:

  • The bubbleSort method takes an integer array arr as input.
  • n stores the length of the array.
  • The outer loop iterates from i = 0 to n - 2. Each pass makes sure the largest unsorted element “bubbles up” to its correct spot at the end of the array.
  • The inner loop goes from j = 0 to n - i - 2, comparing items that are next to each other.
  • If arr[j] is bigger than arr[j + 1], they are swapped using a temporary variable temp.
  • The printArray method is a helper function to show the array’s contents.

Sorting in Descending Order

To sort from largest to smallest, you only need to change the comparison in the inner loop.

public class BubbleSortDescending {
  public static void bubbleSortDescending(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        // Modified condition for descending order
        if (arr[j] < arr[j + 1]) {
          // Swap arr[j] and arr[j+1]
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }

  // Utility method to print array
  public static void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    System.out.println("Original array:");
    printArray(arr);

    bubbleSortDescending(arr); // Call bubble sort method for descending order

    System.out.println("Sorted array (descending order):");
    printArray(arr);
  }
}

The main difference here is the if (arr[j] < arr[j + 1]) condition. Instead of swapping if the current element is greater than the next, we swap if it’s less than the next, effectively sorting in reverse order.

Optimized Bubble Sort

We can make bubble sort faster by stopping it early if no swaps happen during a pass. If no swaps occur, it means the array is already sorted.

public class OptimizedBubbleSort {
  public static void optimizedBubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped; // Flag to check if any swap occurred

    for (int i = 0; i < n - 1; i++) {
      swapped = false;  // Reset swapped flag before each pass

      for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          // Swap arr[j] and arr[j+1]
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
          swapped = true; // Set swapped to true because a swap occurred
        }
      }

      // If no two elements were swapped in inner loop, the array is sorted
      if (swapped == false) {
        break; // Break the outer loop, as array is sorted
      }
    }
  }

  // Utility method to print array
  public static void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    System.out.println("Original array:");
    printArray(arr);

    optimizedBubbleSort(arr); // Call optimized bubble sort method

    System.out.println("Sorted array:");
    printArray(arr);
  }
}

Explanation of the Optimization:

  • A boolean variable swapped is used. It starts as false at the beginning of each pass (outer loop).
  • If a swap happens in the inner loop, swapped becomes true.
  • After each pass, if swapped is still false, no swaps were made. This means the array is sorted as all adjacent elements are relatively in order, and we can stop the outer loop using break.

Sorting Custom Objects

To sort objects you’ve created, you need to tell Java how to compare them. You can do this using the Comparable interface or a Comparator. Let’s explore how to sort using Comparator. Using a Comparator is useful because it lets you define different ways to sort objects without changing the object’s class itself.

import java.util.Arrays;
import java.util.Comparator;

class Person {
  String name;
  int age;

  public Person(String name, int age) {
    this.name = name;
    this.age = age;
  }

  @Override
  public String toString() {
    return name + " (" + age + ")";
  }
}

public class BubbleSortCustomObjects {
  public static void bubbleSort(Person[] arr, Comparator<Person> comparator) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        // Use comparator to compare Person objects
        if (comparator.compare(arr[j], arr[j + 1]) > 0) {
          // Swap arr[j] and arr[j+1]
          Person temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }

  public static void main(String[] args) {
    Person[] people = {
      new Person("Alice", 30),
      new Person("Bob", 25),
      new Person("Charlie", 35),
      new Person("David", 20)
    };

    System.out.println("Original array:");
    System.out.println(Arrays.toString(people));

    // Define a comparator for comparing Person objects by age
    Comparator<Person> ageComparator = Comparator.comparingInt(p -> p.age);

    bubbleSort(people, ageComparator);

    System.out.println("Sorted array by age:");
    System.out.println(Arrays.toString(people));
  }
}

Key points:

  • The Person class no longer implements the Comparable<Person> interface.
  • A Comparator<Person> is created using Comparator.comparingInt(p -> p.age). This creates a comparator that compares Person objects based on their age. The comparingInt method is used for comparing integer values, and p -> p.age is a lambda expression that extracts the age from a Person object.
  • The bubbleSort method now takes an array of Person objects and a Comparator<Person> as arguments.
  • The comparison inside the inner loop uses comparator.compare(arr[j], arr[j + 1]) > 0 to compare Person objects using the provided comparator.
  • We pass the ageComparator to the bubbleSort method to sort the people array by age.

What’s Next?

Now that you’ve learned how to implement bubble sort in Java, you might want to explore: