Bubble Sort in Java

Bubble Sort is one of the easiest and most fun ways to learn sorting. It works by moving larger numbers to the end step by step, like bubbles rising to the top. It is not the fastest method, but it is great for beginners to understand how sorting works. It just needs two loops and a few simple swaps to sort everything. If Bubble Sort is so simple and done in-place, then why is it not used in real-world systems?

In this article, we will discuss the Bubble Sort algorithm in detail.

Table of Contents:

• What is Bubble Sort in Java?
• Bubble Sort Algorithm Java
• Writing Bubble Sort Program in Java
• Optimized Bubble Sort in Java
• Time and Space Complexity of Bubble Sort
• Why the name Bubble Sort?
• Bubble Sort in Java: Sort Numbers and Strings
  • Bubble Sort Ascending Order Java For Numbers
  • Bubble Sort Ascending Order Java For Strings
  • Bubble Sort in Descending Order For Numbers
  • Bubble Sort in Descending Order For Strings
• Advantages of Bubble Sort
• Disadvantages of Bubble Sort
• Conclusion

What is Bubble Sort in Java?

Bubble Sort in Java is one of the simplest ways to sort a list of elements, like numbers or strings. It continuously compares the adjacent items and swaps them if they are in the wrong order, so bigger elements called “bubbles” move to the end of the list. It sorts the array from the lowest to the highest value.

This sorting algorithm is easy for students to understand, is simple, and helps to build the basic concept, even though it is slow for large amounts of data.

Master Java Today - Accelerate Your Future

Enroll Now and Transform Your Future

Explore Program

Bubble Sort Algorithm Java

for pass = 1 to n - 1: // outer loop for comparing passes
    swapped = false
    for i = 0 to n - pass - 1:
        if array[i] > array[i + 1]: //Inner loop for comparing adjacent elements
            swap array[i], array[i + 1]
            swapped = true
    if swapped == false:
        break

In the above algorithm,

• n is the number of elements in the array.
• i is the loop index.
• The swapped variable is used to check if any elements were swapped in a pass.
• array[i] is the position of the array at index i.

Dry Run of the Above Algorithm

Let’s take an example array:

array = [5, 3, 1, 4]

The length of the array is n = 4.

Hence, there will be a total of n - 1 = 3 passes in Bubble Sort.

Pass 1

• Initialize swapped = false
• i = 0: Compare 5 and 3 -> 5 > 3
  • Swap -> array = [3, 5, 1, 4]
  • Set swapped = true
• i = 1: Compare 5 and 1 -> 5 > 1
  • Swap -> array = [3, 1, 5, 4]
  • swapped = true
• i = 2: Compare 5 and 4 -> 5 > 4
  • Swap -> array = [3, 1, 4, 5]
  • swapped = true

End of Pass 1

Pass 2

• Initialize swapped = false
• i = 0: Compare 3 and 1 -> 3 > 1
  • Swap -> array = [1, 3, 4, 5]
  • swapped = true
• i = 1: Compare 3 and 4 -> 3 < 4 -> No swap
• i = 2: Compare 4 and 5 -> 4 < 5 -> No swap

End of Pass 2

Pass 3

• Initialize swapped = false
• i = 0: Compare 1 and 3 -> 1 < 3 -> No swap
• i = 1: Compare 3 and 4 -> 3 < 4 -> No swap
• i = 2: Compare 4 and 5 -> 4 < 5 -> No swap

Since swapped = false throughout this pass, the array is already sorted, and the algorithm terminates early.

End of Pass 3

Final Sorted Array:

[1, 3, 4, 5]

We used the swapped flag to detect that the array was already sorted after the second pass. However, as a safety check, Pass 3 still runs but makes no swaps, confirming the array is sorted.

Writing Bubble Sort Programs in Java

Now, let us discuss the Java program to write a bubble sort:

Example:

Output:

Explanation:

The above Java program is the simplest version of the Bubble Sort. It will run even if the array is already sorted. It always does n-1 passes and compares all elements.

Optimized Bubble Sort in Java

As the above code was running for all the iterations, even if the array is already sorted. Now, let us try to optimize the above code. Here, a swapped flag is used, which stops the number of passes if no elements are swapped in a pass, early. It saves time if the array is already sorted or almost sorted.

Example:

Output:

Time and Space Complexity of Bubble Sort

Time complexity tells us how the number of operations grows as the input size n increases.

In Bubble Sort, we use two loops; the outer loop that runs n-1 times and the inner loop that compares the adjacent elements and swaps them when required.

For Best Case:

The best case in Bubble Sort occurs when the elements in the array are already sorted, because the swapped flag remains false, which means that no elements were swapped. Hence, the outer loop only runs once. So only (n – 1) comparisons and 0 swaps are made.

Time Complexity: O(n)

For Average Case:

The average case of Bubble Sort occurs when the elements in the array are in random order, because all pairs are compared multiple times, and about n(n – 1) / 2 comparisons are made.

Time Complexity: O(n²)

For Worst Case:

The worst case in Bubble Sort occurs when the elements in the array are sorted in reverse order because each element has to be compared and swapped every time. This takes the maximum number of comparisons and swaps.

Time Complexity: O(n²)

Space Complexity of Bubble Sort in Java

Bubble Sort is an in-place sorting algorithm, which means it does not use any extra data structures like arrays, lists, or stacks for sorting. The only additional space used is for the loop variables (i, pass), a swapped boolean flag, and a temp variable for swapping.

Space Complexity: O(1)

Why the name Bubble Sort?

Bubble Sort works by comparing each pair of neighboring elements, if they are in the wrong order, it swaps them.

1. Heavy Elements Sink, Light Ones Rise, just Like Bubbles: In each pass, the largest unsorted element moves to its correct position at the end. Just like in water, lighter bubbles rise to the top. In Bubble Sort, the larger values – metaphorically called “bubbles” – move to the end or to the ‘top’ of the array.
2. Multiple Passes Until Sorted: On each pass, the algorithm “floats” the next largest element into its place, and after each round, the algorithm makes it range shorter by ignoring that the sorted element is at its correct position, i.e., to the end of the list.

Bubble Sort in Java: Sort Numbers and Strings

Bubble Sort in Java can be implemented in ascending as well as in descending order, also with numbers and strings. For numbers, it compares the numerical value, and in the case of a string, it compares the words or letters using dictionary order.

For example, the array [“dog”, “cat”, “apple”]. After sorting, it will become [“apple”, “cat”, “dog”].

Now, let us see the code example for both numbers and strings in ascending as well as in descending order.

1. Sorting Numbers in Ascending Order Using Bubble Sort in Java

Output:

The above Java program compares each pair of elements and swaps if the left number is bigger than the right one. Each pass pushes the largest number to the end, and finally, it prints the sorted array from the smallest to the largest.

2. Sorting Strings in Ascending Order Using Bubble Sort in Java

Output:

The above Java program sorts strings alphabetically and uses the compareTo() method to compare each pair of strings. If a word comes after the next one in dictionary order, it swaps it, and after all the passes, the strings are printed from A to Z.

3. Sorting Numbers in Descending Order Using Bubble Sort in Java

Output:

The above Java program sorts numbers from largest to smallest. It compares each pair and swaps if the left number is smaller than the number to its right. Each pass moves the largest number to the starting and then the result is an array in descending order.

4. Sorting Strings in Ascending Order Using Bubble Sort in Java

Output:

The above Java program sorts the strings in reverse order and swaps the strings if the first one is smaller than the second one. It uses the .compareTo() method to decide the order between the words.

Advantages of Bubble Sort

• Simple to Understand and Implement: Bubble Sort is very easy to understand and code. It is great for beginners to learn sorting logic.
• Works In-Place: It does not need extra memory, because it sorts the elements of the array without using the extra space.
• Detects Already Sorted Arrays: The optimized version of the Bubble Sort has a time complexity of O(n) if the array is already sorted.
• Good for Small Datasets: It works well when the number of elements in the array is very small.

Disadvantages of Bubble Sort

• Very Slow on Large Datasets: It compares every pair of elements, even if the array is sorted.
• Time Complexity is Poor in the Worst Case: It does not work good, if the size of the input is large.
• Many Unnecessary Swaps: Bubble Sort makes a lot of swaps, due to which it is slow as compared to other algorithms.
• Not Used in Real-World Applications: Due to its poor performance, it is not used in practical or commercial software projects.

Unlock Your Future in Java

Start Your Java Journey for Free Today

Explore Program

Conclusion

Bubble Sort in Java is a simple and easy-to-understand way to sort numbers or words, which works by comparing the side-by-side values and then swapping them if they are in the wrong order. This process is repeated until every element is sorted. It is great for learning and small tasks, but not good for big datasets because it takes more time. The improved version of the Bubble Sort can stop early if the list is already sorted. But it is good for practice, but is not used much in real-world projects.

If you want to learn more about this topic, you can refer to our Java course.

Bubble Sort in Java – FAQs