Learn Bubble Sort in Java: Easy Sorting Technique Explained

Step 1: Start with an Unsorted Array

Take an array of numbers that need to be sorted in ascending order. This will be the input for the sorting process.

Step 2: Set Up the Outer Loop

Create a loop that will be run several times to guarantee that all elements are sorted. The number of passes required is the number of elements less than in the array.

Step 3: Compare Adjacent Elements

For each passage, compare two adjacent elements. See if the current one exceeds the next one.

Step 4: Swap If Needed

In case the current element is larger, exchange it with the next one. By doing this, larger numbers are pushed toward the end of the array.

Step 5: Repeat Until the End of the Array

Continue comparing and swapping adjacent elements until the pass is complete. After each full pass, the largest unsorted number settles in its correct position at the end.

Step 6: Reduce the Comparison Range

Sort elements in such a way that the number of comparisons in each subsequent pass is lowered as well. The last sorted elements cannot be checked anymore.

Step 7: Check If Sorting is Done

Use a flag (e.g., swapped) that indicates whether any swaps have been done in a pass. The absence of swaps means that the array is ​‍​‌‍​‍‌​‍​‌‍​‍‌sorted.

Step 8: Stop When Sorted

The algorithm stops when no swaps are needed or after completing all necessary passes. At this point, the array is sorted in ascending order.

Step-by-Step Example

The​‍​‌‍​‍‌​‍​‌‍​‍‌ elements of an array will be rearranged with the help of the Bubble Sort algorithm. Think about the array: [1, 4, 2, 5, -2, 3]. These numbers will be set in order from the least to the greatest by applying Bubble Sort in Java. The process is carried out through many iterations by comparing the elements next to each other and exchanging their places if necessary until the list becomes sorted, which is the same way Bubble Sort in a Java program ​‍​‌‍​‍‌​‍​‌‍​‍‌works.

First Pass:

• Compare 1 and 4 → No change: [1, 4, 2, 5, -2, 3]
• Compare 4 and 2 → Swap: [1, 2, 4, 5, -2, 3]
• Compare 4 and 5 → No change: [1, 2, 4, 5, -2, 3]
• Compare 5 and -2 → Swap: [1, 2, 4, -2, 5, 3]
• Compare 5 and 3 → Swap: [1, 2, 4, -2, 3, 5]

Second Pass:

• Compare 1 and 2 → No change: [1, 2, 4, -2, 3, 5]
• Compare 2 and 4 → No change: [1, 2, 4, -2, 3, 5]
• Compare 4 and -2 → Swap: [1, 2, -2, 4, 3, 5]
• Compare 4 and 3 → Swap: [1, 2, -2, 3, 4, 5]

Third Pass:

• Compare 1 and 2 → No change: [1, 2, -2, 3, 4, 5]
• Compare 2 and -2 → Swap: [1, -2, 2, 3, 4, 5]
• Compare 2 and 3 → No change: [1, -2, 2, 3, 4, 5]

Fourth Pass:

• Compare 1 and -2 → Swap: [-2, 1, 2, 3, 4, 5]

Pseudocode for Bubble Sort Algorithm

Below is clear pseudocode for Bubble Sort in ascending order:

Bubble Sort Pseudocode (Ascending Order)

function bubbleSort(array):
    n = length of array

    for k from 0 to n - 1:
        for m from 0 to n - k - 2:
            if array[k] > array[m + 1]:
                swap(array[m], array[m + 1])

Optimized Bubble Sort in Java – Pseudocode (Early Exit)

function bubbleSort(array):
n = length of array
for i from 0 to n - 1:
swapped = false
for j from 0 to n - i - 2:
if array[j] > array[j + 1]:
swap(array[j], array[j + 1])
swapped = true
if not swapped:
Break

Descending Order (Java-Style Pseudocode)

bubbleSort(arr)
    n ← length of arr

    for i ← 0 to n - 2
        for j ← 0 to n - i - 2
            if arr[j] < arr[j + 1]
                swap(arr[j], arr[j + 1])

Key Terms

• bubble sort algorithm (pseudocode): The step-by-step logic for Bubble Sort, written in human-readable instructions.
• array of size n: The input sequence to be sorted.
• ascending order / descending order: The desired final arrangement of the elements.
• swap(array[j], array[j + 1]): The operation that exchanges two adjacent elements when they are out of order.

Here is a Java program demonstrating Bubble Sort, a basic method to sort elements from smallest to largest. The algorithm compares each pair of neighboring items and swaps them when they are not in the correct order. This cycle repeats until the whole array is properly sorted. Bubble Sort is easy to grasp and commonly used as an introductory sorting algorithm for learners.

Bubble Sort Code in Java 

Here is a simple example of how to implement Bubble Sort in Java, along with a clear explanation to help you understand how it works.

public class BubbleSortExample {
    public static void main(String[] args) {
        int[] numbers = {7, 3, 9, 1, 5};  
        bubbleSort(numbers);  

        System.out.println("Sorted Array:");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;
        for (int k = 0; k < size - 1; k++) {
            for (int j = 0; j < size - 1 - k; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

Explanation:

The program starts with an unsorted array and sorts it using Bubble Sort in Java. It goes through the array multiple times by comparing and swapping the adjacent elements if they are in the incorrect order. Just like implementing Bubble Sort in Java program, with each full pass, the largest unsorted number moves to its correct position. The process continues until the array is completely sorted.

Output:

Sorted Array:  
1 3 5 7 9 

Time And Space Complexity:

• Time Complexity: Worst and Average Case: O(n²), Best Case (Already Sorted): O(n)
• Space Complexity: O(1) (In-place sorting, no extra space used)

While the basic Bubble Sort algorithm is easy to understand, it can be inefficient for large datasets or arrays that are already nearly sorted. To improve its performance and reduce unnecessary comparisons and exchanges, several optimizations and variations can be applied.

Early Termination (Optimized Bubble Sort)

One of the most effective optimizations is early termination.
In the standard Bubble Sort, the algorithm continues to run for all passes even if the array becomes sorted before completion. To avoid this, a boolean flag is used to track whether any exchanges (swaps) occur during a pass.

If no swaps are made in an entire pass, it indicates that the array is already sorted, and the algorithm can stop immediately. This significantly improves performance for nearly sorted or already sorted input.

How Early Termination Works:

• Introduce a boolean variable, such as swapped or isSwapped
• Set the flag to false at the beginning of each pass
• Set it to true whenever an exchange occurs
• After completing a pass:
  
  • If the flag remains false, terminate the algorithm early

This technique is commonly referred to as optimized bubble sort or the early exit strategy.

Steps Quantity (Pass Reduction)

Optimized Bubble Sort also reduces the steps quantity, meaning the number of passes and comparisons required to sort the array.

• Best Case (Already Sorted Array):
  Only one pass is required, and no exchanges occur.
• Worst Case (Reverse Sorted Array):
  It is the situation in which the maximum number of passes is made, as the elements have to be exchanged one by one to their correct positions.

By eliminating the needless passes, the algorithm's efficiency is elevated to a certain extent, although its fundamental logic remains ​‍​‌‍​‍‌​‍​‌‍​‍‌unchanged.

Alternative Implementations

Bubble Sort can be implemented in multiple ways while preserving its behavior:

• Using nested for loops with a swap flag for early termination
• Using while loops instead of for loops
• Tracking the last index where an exchange occurred to further reduce the comparison range in subsequent passes

These variations help minimize redundant comparisons but do not change the overall worst-case time complexity.

Java Implementation of Optimized Bubble Sort

public class SmartBubbleSort {

    public static void optimizedSort(int[] nums) {
        int length = nums.length;
        boolean isSwapped;

        // Outer loop for passes
        for (int pass = 0; pass < length - 1; pass++) {
            isSwapped = false;

            // Inner loop to compare adjacent elements
            for (int index = 0; index < length - pass - 1; index++) {
                if (nums[index] > nums[index + 1]) {
                    // Perform exchange
                    int temp = nums[index];
                    nums[index] = nums[index + 1];
                    nums[index + 1] = temp;
                    isSwapped = true;
                }
            }

            // Early termination if no exchanges occurred
            if (!isSwapped)
                break;
        }
    }

    // Method to display array elements
    public static void showArray(int[] nums) {
        for (int val : nums)
            System.out.print(val + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] sampleData = {64, 34, 25, 12, 22, 11, 90};

        System.out.println("Array before sorting:");
        showArray(sampleData);

        optimizedSort(sampleData);

        System.out.println("Array after sorting:");
        showArray(sampleData);
    }
}

Explanation

The​‍​‌‍​‍‌​‍​‌‍​‍‌ SmartBubbleSort program is a clear example of an optimized solution for Bubble Sort in Java. It goes through the array by comparing adjacent elements and doing an exchange only if it is necessary. The isSwapped flag helps the program to go on with the execution before the end of the run, depending on the fact that if no elements are swapped in a pass, the array is already sorted. Thus, it eliminates those operations that are redundant and makes the algorithm run faster with datasets that are almost ​‍​‌‍​‍‌​‍​‌‍​‍‌sorted.

Output

Array before sorting: 64 34 25 12 22 11 90
Array after sorting: 11 12 22 25 34 64 90

Bottom Line

Optimized Bubble Sort improves the algorithm performance by figuring out that the number of passes that can be done is limited, it still keeps the core behavior and worst-case complexity of the algorithm ​‍​‌‍​‍‌​‍​‌‍​‍‌unchanged.

To fully learn the efficiency of Bubble Sort, one has to look at its time and space complexity in various ​‍​‌‍​‍‌​‍​‌‍​‍‌cases.

Time Complexity

Bubble Sort’s time complexity depends on the initial order of the input data and whether the optimized version is used:

• Best-Case Scenario (Already Sorted Array):
  When the array is already sorted, the optimized Bubble Sort will detect that no swaps are needed and stop after one pass.
  Time Complexity: O(n)
• Average-Case Scenario (Random Order):
  For a randomly ordered array, Bubble Sort compares every pair of adjacent elements in multiple passes, leading to a quadratic number of comparisons and swaps.
  Time Complexity: O(n²)
• Worst-Case Scenario (Reverse Sorted Array):
  When​‍​‌‍​‍‌​‍​‌‍​‍‌ the array is sorted in the reverse order, Bubble Sort will carry out the greatest number of comparisons and swaps. Every element has to be bubbled down to its rightful ​‍​‌‍​‍‌​‍​‌‍​‍‌place.

Time Complexity: O(n²)

Summary Table:

Space Complexity

• Auxiliary Space:
  Bubble Sort is an in-place sorting algorithm. It only uses a constant amount of extra memory (for temporary variables during swapping), regardless of input size.
  Space Complexity: O(1)

Relevant Terms Explained

• O(1): Constant time or space—does not grow with input size.
• O(n): Linear time—operations grow proportionally with the number of elements.
• O(n²): Quadratic time—operations grow with the square of the input size.
• In-place Sorting: Sorting is done within the original array, without needing extra storage.
• Auxiliary Space: Additional memory used by the algorithm, beyond the input data.
• Stable Algorithm: Maintains the relative order of equal elements.

Key Points

• Bubble​‍​‌‍​‍‌​‍​‌‍​‍‌ Sort is a great choice when working with small or almost sorted data, in particular if you take an optimized version of it. 
• If you have a large or reverse-ordered array, its speed will get worse drastically due to its O(n²) time complexity. 
• Also, the algorithm uses very little memory and allows for O(1) extra space ​‍​‌‍​‍‌​‍​‌‍​‍‌only.

The table below compares Bubble Sort with commonly used sorting algorithms to highlight differences in time complexity, space complexity, memory usage, and practical use cases.

Sorting Algorithms Comparison Table

Memory Usage & Space Complexity 

• Bubble Sort and Insertion Sort use O(1) space complexity, meaning they do not require extra memory.
• Merge Sort uses O(n) space, which increases memory usage.
• Quick Sort uses O(log n) space due to recursive calls.
• Java’s built-in sorting methods are memory-efficient and optimized internally.

Summary

• Bubble Sort has the highest time complexity (O(n²)), which makes it slow for large datasets.
• Optimized Bubble Sort can run in O(n) (linear time) when the array is already sorted.
• Insertion Sort is also O(n²), but it usually performs fewer swaps and is faster than Bubble Sort for small or nearly sorted data.
• Merge Sort always runs in O(n log n) time, making it very efficient for large datasets, but it requires extra memory.
• Quick Sort is one of the fastest algorithms in practice, but its worst-case time complexity can reach O(n²).
• Built-in Java sort methods are optimized and should be preferred over manual sorting algorithms in production code.

• Easy to Learn and Implement: Bubble Sort is one of the simplest sorting techniques, making it a great choice for beginners learning how sorting algorithms work. Its step-by-step approach is easy to grasp.
• No Extra Memory Needed: This sorting method works directly on the given list without requiring extra storage space. Since it sorts the elements in place, it is memory-efficient.
• Maintains Order of Equal Elements (Stable Sorting): If two elements have the same value, Bubble Sort keeps them in their original order, which is useful in cases where maintaining the sequence of identical items is important.
• Detects Already Sorted Arrays Quickly: Bubble Sort can recognize if the array is already sorted and stop early, which saves time in best-case scenarios.
• Simple to Modify for Different Sorting Needs: Due to its straightforward logic, Bubble Sort can be easily adapted or combined with other algorithms for specific requirements or educational purposes.

Bubble​‍​‌‍​‍‌​‍​‌‍​‍‌ Sort is an elementary sorting algorithm. However, its use is mostly limited because of its performance. Knowing the time and reasons for using or not using Bubble Sort is an essential programming skill.

1. Educational Purposes
   One common use of Bubble Sort is as a learning tool to help students grasp the idea of sorting, algorithm creation, and complexity ​‍​‌‍​‍‌​‍​‌‍​‍‌evaluation. Its straightforward logic makes it an excellent first algorithm for beginners.
2. Small Input Sizes
   For very small datasets, Bubble Sort can be sufficient. Its simplicity can sometimes outweigh the need for efficiency in cases where the list contains only a handful of elements.
3. Nearly Sorted Data (Best Case Scenario)
   When the input array is already sorted or nearly sorted, the optimized version of Bubble Sort can finish quickly—sometimes in linear time (O(n)). This is because the algorithm can detect that no swaps are needed and terminate early.
4. Code Simplicity Over Performance
   In scenarios where code readability and simplicity are more important than raw performance, Bubble Sort’s easy-to-understand structure can be an advantage.
5. Stability Requirement
   Bubble​‍​‌‍​‍‌​‍​‌‍​‍‌ Sort keeps the ordering of elements which have the same value (it is stable), which is a feature that is occasionally required in cases where the sequencing of the duplicates is of importance.

Limitations and When to Avoid Bubble Sort

• Large Datasets
  Bubble Sort is a method that is not suitable for large input sizes. Both its average and worst-case time complexity are O(n²), which results in extremely slow performance when the data set becomes large.
• Performance-Critical Applications
  n the case of speed and efficiency real-world applications, the use of Bubble Sort is not recommended. More advanced algorithms like Quick Sort, Merge Sort, or Java’s built-in sorting methods are much more suitable.
• Unnecessary Comparisons
  Even for nearly sorted data, the basic version of Bubble Sort performs unnecessary passes unless optimized. For reverse-ordered data (worst case), it will take the maximum number of passes and swaps.
• Rare Real-World Usage
  Bubble Sort is almost never used in production systems. Its main value is in education, demonstrations, or extremely simple, non-critical scripts.

In summary, Java Bubble Sort would be a great tool for a beginner to learn with, for some small tasks, to try out some code, or to simply do a job of a few items when you are not concerned with the performance. The thing is: most of the time, in real-life and practical situations, a better sorting algorithm is the most suitable ​‍​‌‍​‍‌​‍​‌‍​‍‌one.

Bubble Sort in Java is a basic sorting method that may not be the best choice for large datasets because it is slow compared to other sorting techniques. However, it is a great way to learn how sorting works, making it valuable for beginners. By understanding and practicing Bubble Sort in Java, programmers can develop a solid grasp of sorting principles, which will help them learn more advanced and efficient sorting methods in the future.

Points to Remember 

1. Bubble Sort in Java compares adjacent elements and swaps them until the array is sorted.
2. Each pass moves the largest unsorted element to the end of the array.
3. Optimized Bubble Sort in Java can stop early, giving O(n) time in the best case.
4. Bubble Sort is stable and in-place, meaning it preserves order and uses O(1) space.
5. Bubble Sort in Java is great for learning, but not for real-world performance.

1. Is Bubble Sort stable?

Yes, Bubble Sort maintains stability in sorting. If two elements are equal, their original order is preserved after sorting.

2. What are the typical use cases for Bubble Sort in Java?

Bubble Sort is mostly used as a teaching tool and for sorting very small datasets. It is not recommended for large or performance-critical applications.

3. Why is Bubble Sort considered inefficient for large datasets?

Bubble Sort time complexity is O(n²) for both average and worst cases, thus its performance deteriorates very quickly as the dataset increases. More advanced algorithms like Quick Sort or Merge Sort are much faster for large datasets.

4. How can Bubble Sort be optimized in Java?

You can optimize Bubble Sort by adding a flag to check if any swaps occurred during a pass. If no swaps are made, the algorithm stops early, which is helpful for already sorted or nearly sorted arrays.

5. Does Bubble Sort use extra memory?

No, Bubble Sort is an in-place sorting algorithm and only needs a constant amount of extra space for temporary variables (space complexity O(1)).

6. What is the best-case scenario for Bubble Sort in Java?

The best case occurs when the array is already sorted. With the optimized version, Bubble Sort will detect this in the first pass and finish early, resulting in O(n) time complexity.