How to do Bubble Sort in Java

Sorting algorithms are fundamental to programming, and Bubble Sort is one of the simplest algorithms to understand and implement. In this blog post, we’ll discuss how to implement Bubble Sort in Java and its time and space complexities and explore when the algorithm is appropriate to use.

What is Bubble Sort?

Bubble Sort is a comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until no swaps are needed, indicating that the list is sorted.

Below, you can see a visualization of how Bubble Sort works. Choose the length of your array in the box next to Array Size (Max 30) then click Generate Random Array to generate the numbers, then click Start Sorting.

Time Complexity of Bubble Sort

• Best Case: O(n)—When the array is already sorted, Bubble Sort only needs to make one pass through it, making it O(n).
• Average Case: O(n²) – On average, the algorithm compares each element with each other, resulting in quadratic complexity.
• Worst Case: O(n²) – In the worst-case scenario, where the array is in reverse order, Bubble Sort has to make the maximum number of swaps, resulting in O(n²).

Space Complexity of Bubble Sort

• Space Complexity: O(1) – Bubble Sort is an in-place sorting algorithm requiring a constant amount of extra memory, regardless of the input size.

Pseudocode for Bubble Sort

The pseudocode for Bubble Sort outlines the basic steps of the algorithm:

procedure bubbleSort(arr)
    n = length(arr)
    repeat
        swapped = false
        for i = 0 to n-2 do
            if arr[i] > arr[i+1] then
                swap(arr[i], arr[i+1])
                swapped = true
        n = n - 1
    until swapped = false

Step-by-Step Explanation:

• You iterate through the array multiple times.
• During each pass, adjacent elements are compared, and if they are out of order, they are swapped.
• This process is repeated until no swaps occur during a complete pass, meaning the array is fully sorted.

Java-Specific Idiosyncrasies

When implementing Bubble Sort in Java, there are a few things specific to the language that are worth noting:

1. Primitive vs. Object Types:
   • Java distinguishes primitive types (e.g., int, double) and object types (e.g., Integer, Double). Bubble Sort will work differently depending on whether you’re sorting arrays of primitives or objects.
   • For primitive arrays (like int[]), comparisons are faster because Java doesn’t deal with unboxing.
   • For arrays of objects (like Integer[]), additional overhead comes from Java’s unboxing and boxing process when comparing or swapping values.
2. Pass-by-Value:
   • Java uses pass-by-value for primitive data types and pass-by-reference for objects. However, for arrays, Java passes the reference to the array, meaning changes made inside the method affect the original array. This is useful in sorting algorithms like Bubble Sort because you don’t need to return the sorted array; the original array is modified directly.
3. Array Access Performance:
   • Accessing elements in an array in Java is quite efficient, but if you’re sorting large arrays of non-primitive types (like Integer instead of int), Java’s auto-boxing can introduce some performance overhead. This is especially noticeable in Bubble Sort, where numerous comparisons and swaps happen repeatedly.
4. Memory Usage:
   • Since Bubble Sort doesn’t require additional data structures beyond the array, its space complexity is O(1). Java handles memory efficiently for this algorithm, though using arrays of primitives (like int[]) can reduce memory overhead compared to arrays of object types (Integer[]).
5. No Built-in Method for Swapping Elements:
   • Unlike languages like Python or C++, Java does not have a built-in method for swapping two elements. You must manually implement the swap operation using a temporary variable in Java.

Java Implementation of Bubble Sort

Here is how you can implement Bubble Sort in Java:

public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        // Outer loop for all elements
        for (int i = 0; i < n - 1; i++) {
            swapped = false;

            // Inner loop for comparing adjacent elements
            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;
                }
            }

            // If no elements were swapped, the array is already sorted
            if (!swapped) break;
        }
    }

    // Helper method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

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

Output:

Unsorted array:
64 34 25 12 22 11 90 
Sorted array:
11 12 22 25 34 64 90 

Step-by-Step Explanation of Example

Initial Array: [64, 34, 25, 12, 22, 11, 90]

Outer loop (i = 0):

1. Compare 64 and 34: Since 64 > 34, swap them.
   Array after swap: [34, 64, 25, 12, 22, 11, 90]
2. Compare 64 and 25: Since 64 > 25, swap them.
   Array after swap: [34, 25, 64, 12, 22, 11, 90]
3. Compare 64 and 12: Since 64 > 12, swap them.
   Array after swap: [34, 25, 12, 64, 22, 11, 90]
4. Compare 64 and 22: Since 64 > 22, swap them.
   Array after swap: [34, 25, 12, 22, 64, 11, 90]
5. Compare 64 and 11: Since 64 > 11, swap them.
   Array after swap: [34, 25, 12, 22, 11, 64, 90]
6. Compare 64 and 90: No swap, since 64 < 90.

After the first pass, the largest element (90) has bubbled to its correct position.

---

Outer loop (i = 1):

1. Compare 34 and 25: Since 34 > 25, swap them.
   Array after swap: [25, 34, 12, 22, 11, 64, 90]
2. Compare 34 and 12: Since 34 > 12, swap them.
   Array after swap: [25, 12, 34, 22, 11, 64, 90]
3. Compare 34 and 22: Since 34 > 22, swap them.
   Array after swap: [25, 12, 22, 34, 11, 64, 90]
4. Compare 34 and 11: Since 34 > 11, swap them.
   Array after swap: [25, 12, 22, 11, 34, 64, 90]
5. Compare 34 and 64: No swap since 34 < 64.

Now, the second largest element (64) is in its correct position.

---

Outer loop (i = 2):

1. Compare 25 and 12: Since 25 > 12, swap them.
   Array after swap: [12, 25, 22, 11, 34, 64, 90]
2. Compare 25 and 22: Since 25 > 22, swap them.
   Array after swap: [12, 22, 25, 11, 34, 64, 90]
3. Compare 25 and 11: Since 25 > 11, swap them.
   Array after swap: [12, 22, 11, 25, 34, 64, 90]
4. Compare 25 and 34: No swap, since 25 < 34.

The third largest element (34) is in its correct position.

---

Outer loop (i = 3):

1. Compare 12 and 22: No swap since 12 < 22.
2. Compare 22 and 11: Since 22 > 11, swap them.
   Array after swap: [12, 11, 22, 25, 34, 64, 90]
3. Compare 22 and 25: No swap since 22 < 25.

The fourth largest element (25) is in its correct position.

---

Outer loop (i = 4):

1. Compare 12 and 11: Since 12 > 11, swap them.
   Array after swap: [11, 12, 22, 25, 34, 64, 90]
2. Compare 12 and 22: No swap since 12 < 22.

The fifth-largest element (22) is in its correct position.

---

Outer loop (i = 5):

1. Compare 11 and 12: No swap since 11 < 12.

Now, the smallest element (11) is in its correct position.

Sorted Array: [11, 12, 22, 25, 34, 64, 90]

---

Key Points:

• After each pass, the largest unsorted element “bubbles” to its correct position.
• The number of comparisons decreases with each iteration because the last elements are already sorted.
• Bubble Sort performs best when the array is nearly sorted, but its time complexity is generally inefficient for large arrays.

Performance Test: Bubble Sort vs Arrays.sort() in Java

While Java is known for its portability and ease of use, it is not the most performant language for low-level operations like sorting. To illustrate the impact of Java’s characteristics (such as automatic memory management and garbage collection), we’ll compare the performance of Bubble Sort with Java’s highly optimized built-in Arrays.sort() method.

We’ll conduct this test on arrays of different sizes to demonstrate the performance gap and the effects of Java’s runtime environment.

import java.util.Arrays;
import java.util.Random;

public class SortingPerformanceTest {

    // Bubble Sort implementation
    public static void bubbleSort(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; // Optimized: If no elements were swapped, array is sorted
        }
    }

    // Helper method to generate a random array of a given size
    public static int[] generateRandomArray(int size) {
        Random rand = new Random();
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = rand.nextInt(10000); // Random values between 0 and 9999
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] sizes = {1000, 5000, 10000}; // Different array sizes

        for (int size : sizes) {
            // Generate random array
            int[] arr1 = generateRandomArray(size);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length); // Copy for Arrays.sort()

            // Test Bubble Sort performance
            long startTime = System.nanoTime();
            bubbleSort(arr1);
            long endTime = System.nanoTime();
            long bubbleSortDuration = (endTime - startTime) / 1000000; // Convert to milliseconds

            // Test Arrays.sort() performance
            startTime = System.nanoTime();
            Arrays.sort(arr2);
            endTime = System.nanoTime();
            long arraysSortDuration = (endTime - startTime) / 1000000; // Convert to milliseconds

            // Print results
            System.out.println("Array size: " + size);
            System.out.println("Bubble Sort duration: " + bubbleSortDuration + " ms");
            System.out.println("Arrays.sort() duration: " + arraysSortDuration + " ms");
            System.out.println();
        }
    }
}

Results

Array Size	Bubble Sort Duration (ms)	Arrays.sort() Duration (ms)
1000	5	2
5000	31	2
10000	98	1

Analysis of Results

• Bubble Sort is much slower than Arrays.sort() for larger arrays. This is because Bubble Sort has a time complexity of O(n²), meaning the time it takes grows quadratically with the size of the array, whereas Arrays.sort() uses a much more efficient O(n log n) algorithm.
• Java’s Memory Management: Java’s garbage collector doesn’t affect the sorting process directly but introduces some overhead during execution. The more memory Java needs to manage (e.g., with larger arrays), the more work the garbage collector does. In optimized algorithms like Arrays.sort(), the impact of this overhead is minimized, but with Bubble Sort’s inefficiency, this overhead can become more apparent in the total execution time.
• Automatic Memory Management: Java automatically handles memory allocation and deallocation. While this makes Java more accessible to use than languages like C/C++, it also adds some computational overhead that can make algorithms like Bubble Sort perform worse than their C/C++ counterparts.
• Optimized Built-In Methods: Java’s Arrays.sort() is highly optimized for speed and efficiency. It’s always better to use built-in sorting functions for practical applications unless a custom algorithm is required for specific reasons (e.g., learning purposes or unique constraints).

Pros and Cons of Using Bubble Sort

Pros:

• Simplicity: Bubble Sort is one of the most accessible algorithms to understand and implement, making it a good learning tool for beginners.
• In-Place Sorting: It uses O(1) additional space, meaning it doesn’t require any extra data structures.
• Stability: Bubble Sort is a stable sorting algorithm that preserves the relative order of elements with equal keys.

Cons:

• Inefficiency: Its time complexity of O(n²) makes it inefficient for large datasets compared to more advanced algorithms like QuickSort or MergeSort.
• Not Practical: Bubble Sort is rarely used in real-world applications where large data needs to be sorted due to its poor average-case performance.
• Many Comparisons: Even if the array is nearly sorted, Bubble Sort makes unnecessary comparisons unless optimized further.

When to Use Bubble Sort

While Bubble Sort is not typically used in production-level applications due to its inefficiency, it can be useful in the following situations:

• Small Datasets: Bubble Sort’s simplicity can make it a reasonable option for working with very small arrays.
• Teaching and Learning: Bubble Sort is excellent for understanding the basic principles of sorting and how comparison-based algorithms work.
• Stability Requirement: If you need a stable sorting algorithm and performance isn’t a concern, Bubble Sort can be used since it maintains the relative order of equal elements.
• Pre-Sorted Data: In cases where the data is nearly or entirely sorted, Bubble Sort’s best-case performance of O(n) makes it a reasonable choice.

Conclusion

Bubble Sort is one of the simplest sorting algorithms for implementation and conceptual understanding. While it is unsuitable for large datasets due to its O(n²) time complexity, it can still be helpful in specific cases, such as small datasets or learning environments. If you’re working with larger datasets, consider using more efficient algorithms like Merge Sort or QuickSort.

Understanding Bubble Sort is an essential first step in grasping more complex algorithms, and with its straightforward implementation in JavaScript, it’s a great way to start learning about sorting algorithms.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Bubble Sort:

In Python – How to do Bubble Sort in Python

In C++ – How to Do Bubble Sort in C++

In Rust – How to do Bubble Sort in Rust

Have fun and happy researching!