How To Sort The Elements Of An Array Using Bubble Sort In Java

Learning to sort data is a fundamental skill in computer science, and understanding various sorting algorithms is crucial. In this article, you will learn how to sort the elements of an array using the Bubble Sort algorithm in Java, exploring its mechanics and practical implementation.

Problem Statement

Efficiently organizing data is a common requirement in many applications, from databases to user interfaces. When dealing with an unsorted collection of items, such as an array of numbers, the challenge is to arrange them in a specific order (ascending or descending) to facilitate searching, analysis, or presentation. An unsorted array makes it difficult to quickly find minimum/maximum values or perform binary searches.

Example

Consider an unsorted array of integers: [64, 34, 25, 12, 22, 11, 90]. After applying a sorting algorithm like Bubble Sort, the array will be ordered as: [11, 12, 22, 25, 34, 64, 90].

Background & Knowledge Prerequisites

To effectively understand and implement Bubble Sort in Java, readers should have a basic grasp of the following concepts:

• Java Basics:
• Variables and data types (especially integers and arrays).
• Control flow statements (for loops, if statements).
• Method declaration and calling.
• Arrays: Understanding how arrays work, how to declare, initialize, and access elements.
• Algorithms: A general understanding of what an algorithm is and its role in problem-solving.

Use Cases or Case Studies

Sorting algorithms, including Bubble Sort, find application in various scenarios, though Bubble Sort specifically is often used for educational purposes due to its simplicity, rather than for high-performance production systems.

• Educational Demonstrations: Bubble Sort is an excellent algorithm for beginners to learn the basic concepts of sorting due to its straightforward logic.
• Small Datasets: For very small arrays (e.g., fewer than 10-20 elements), the overhead of more complex algorithms might outweigh Bubble Sort's inefficiency, making it a viable, simple choice.
• Nearly Sorted Data: If an array is already mostly sorted, Bubble Sort can perform relatively well as it can terminate early if no swaps occur in a pass.
• Interactive Visualizations: Its step-by-step nature makes it ideal for visual demonstrations of sorting algorithms, helping to understand how elements move into their correct positions.
• Teaching Performance Analysis: Comparing Bubble Sort's O(n^2) complexity with other algorithms like Merge Sort or Quick Sort is a key part of algorithm analysis education.

Solution Approaches

We will explore two approaches for implementing Bubble Sort: a basic version and an optimized version.

1. Basic Bubble Sort Implementation

This approach involves repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted.

One-line summary: Compares and swaps adjacent elements in repeated passes, moving the largest unsorted element to its correct position in each pass.

// Basic Bubble Sort
import java.util.Arrays; // Required for Arrays.toString() to print the array

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array: " + Arrays.toString(arr));

        bubbleSortBasic(arr);

        System.out.println("Sorted array (Basic): " + Arrays.toString(arr));
    }

    // Method to perform basic bubble sort
    public static void bubbleSortBasic(int[] arr) {
        int n = arr.length;
        // Outer loop for passes through the array
        for (int i = 0; i < n - 1; i++) {
            // Inner loop for comparisons and swaps
            // The last i elements are already in place
            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;
                }
            }
        }
    }
}

Run

Sample Output:

Original array: [64, 34, 25, 12, 22, 11, 90]
Sorted array (Basic): [11, 12, 22, 25, 34, 64, 90]

Stepwise Explanation:

1. Initialization: An integer array arr is declared and initialized with unsorted values. The bubbleSortBasic method is called.
2. Outer Loop (i): This loop runs n-1 times, where n is the number of elements in the array. Each iteration of this loop represents a "pass" through the array. After each pass, the largest unsorted element "bubbles up" to its correct position at the end of the unsorted portion of the array.
3. Inner Loop (j): This loop iterates from the first element up to n - i - 1.

• n - i - 1 is used because the last i elements are already sorted and in their final positions from previous passes, so we don't need to compare them again.

1. Comparison and Swap: Inside the inner loop, arr[j] is compared with arr[j+1].

• If arr[j] is greater than arr[j+1], it means they are in the wrong order (for ascending sort).
• A temporary variable temp is used to swap the values of arr[j] and arr[j+1].

1. Iteration: This process continues until the outer loop completes, by which point the entire array is sorted.

2. Optimized Bubble Sort with Flag

The basic Bubble Sort always performs (n-1) passes, even if the array becomes sorted earlier. An optimization can be made by introducing a swapped flag. If no swaps occur during a complete pass, it means the array is already sorted, and we can terminate early.

One-line summary: Enhances basic Bubble Sort by adding a flag to detect if any swaps occurred in a pass, allowing early termination if the array becomes sorted.

// Optimized Bubble Sort
import java.util.Arrays; // Required for Arrays.toString() to print the array

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array: " + Arrays.toString(arr1));
        bubbleSortOptimized(arr1);
        System.out.println("Sorted array (Optimized): " + Arrays.toString(arr1));

        System.out.println("\\nTesting with a nearly sorted array:");
        int[] arr2 = {1, 2, 5, 4, 3}; // Requires fewer passes due to early termination
        System.out.println("Original array: " + Arrays.toString(arr2));
        bubbleSortOptimized(arr2);
        System.out.println("Sorted array (Optimized): " + Arrays.toString(arr2));
    }

    // Method to perform optimized bubble sort
    public static void bubbleSortOptimized(int[] arr) {
        int n = arr.length;
        boolean swapped;
        // Outer loop for passes through the array
        for (int i = 0; i < n - 1; i++) {
            swapped = false; // Reset swapped flag for each pass
            // Inner loop for comparisons and swaps
            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; // Mark that a swap occurred
                }
            }
            // If no two elements were swapped by inner loop, then break
            if (!swapped) {
                break;
            }
        }
    }
}

Run

Sample Output:

Original array: [64, 34, 25, 12, 22, 11, 90]
Sorted array (Optimized): [11, 12, 22, 25, 34, 64, 90]

Testing with a nearly sorted array:
Original array: [1, 2, 5, 4, 3]
Sorted array (Optimized): [1, 2, 3, 4, 5]

Stepwise Explanation:

1. Initialization: Similar to the basic version, but a boolean swapped variable is introduced and initialized to false at the beginning of each outer loop iteration (each pass).
2. Comparison and Swap: The inner loop performs comparisons and swaps just like the basic version. Crucially, if a swap occurs, swapped is set to true.
3. Early Termination Check: After the inner loop (a full pass) completes, the swapped flag is checked.

• If swapped is false, it means no elements were swapped in that entire pass, indicating the array is already sorted.
• In this case, the break statement terminates the outer loop early, preventing unnecessary further passes.

1. Efficiency: This optimization significantly improves performance for nearly sorted or already sorted arrays, as it can reduce the number of passes from n-1 to potentially just one. However, in the worst case (reverse sorted array), it still performs n-1 passes.

Conclusion

Bubble Sort is a simple sorting algorithm, easy to understand and implement, making it an excellent starting point for learning about sorting algorithms. While straightforward, its time complexity of O(n^2) in the worst and average cases means it is not generally suitable for large datasets where efficiency is critical. The optimized version with a flag provides a slight improvement for nearly sorted arrays by allowing early termination.

Summary

• Bubble Sort Fundamentals: Sorts an array by repeatedly comparing and swapping adjacent elements until the entire array is in the desired order.
• Mechanism: In each pass, the largest unsorted element "bubbles up" to its correct position.
• Time Complexity: O(n^2) in the worst and average cases, making it inefficient for large arrays.
• Space Complexity: O(1) as it sorts in-place, requiring minimal extra memory.
• Optimization: A swapped flag can be used to terminate the algorithm early if a pass completes without any swaps, improving performance for nearly sorted arrays.
• Practical Use: Primarily used for educational purposes, very small datasets, or when simplicity outweighs performance concerns.