Bubble Sort Java

If you have ever heard of sorting methods in programming, most likely it was the bubble sort algorithm. It is a famous one. Every programmer knows bubble sort (or at least heard of it while learning) not because it is the best sorting algorithm in the world, but the easiest one. This algorithm is usually used for learning purposes or you may get it as a task in your Java Junior Interview. Java Bubble sort algorithm is very easy to understand, however it is not an efficient one. Anyway, let’s figure it out.

What is sorting

First of all, you need to understand what sorting is in general and what we can sort in Java programs. If we can compare two or more elements or objects by any of their attributes, it means that they can be sorted by this attribute. For example, numbers in ascending or descending order or words alphabetically. Hence, the elements must be comparable with each other. By the way, the elements of what? In Java, we can compare the elements of Collections. For example we can sort Array or ArrayList of integers, Strings and so on.

How does bubble sort work

Let's say, we need to sort an array of integers in ascending order, that is, from the smallest to the biggest number. First, we are going along the entire array and compare every 2 neighboring elements. If they are in the wrong order (the left neighbor is bigger than the right one), we swap them. At the first pass at the end it will appear the biggest element (if we sort in ascending order). You may say, the biggest element “pops up”. That’s the reason of the Bubble sort algorithm name. We repeat the first step from the first to the next-to-last element. We’ve got the second biggest element at the next-to-last place. And so on. We can improve an algorithm a little bit with checking out if at least one exchange at the previous step was made. If it isn’t we stop our running along the array.

Bubble sort example

Let's sort the array of integers, the one, you may see below on a picture. Step 1: we are going through the array. The algorithm starts with the first two elements (with indices 0 and 1), 8 and 7, and checks if they are in the correct order. Obviously, 8 > 7, so we swap them. Next, we look at the second and third elements (indices 1 and 2), now these are 8 and 1. For the same reasons, we swap them. For the third time we compare 8 and 2 and, at least 8 and 5. We made four exchanges in total: (8, 7), (8, 1), (8, 2) and (8, 5). A value of 8, the biggest in this array, popped up at the end of the list to the correct position. The result of the first step of Bubble sort algorithm working is the next array: Step 2. Doing the same with (7,1), (7,2) and (7,5). 7 is now in the penultimate position, and we don’t need to compare it with the "tail" of the list, it is already sorted. The result of the second step of Bubble sort algorithm working is the next array: As you may see, this array is already sorted. Anyway Bubble Sort algorithm should get going at least one more time. Step3. We are going through the array once more. Nothing to swap here, so if we are using “improved” Bubble Sort algorithm (with checking out if at least one exchange at the previous step was made) this step is the last one.

Bubble sort Java code

Bubble sort Java realisation

Let’s create two methods for Bubble sort. The first one, bubbleSort(int[] myArray) is a plane one. It runs through the array every time. The second one, optimizedBubbleSort(int myArray[]) is optimized by stopping the algorithm if inner loop didn’t cause any swap. Counter shows you how many steps did you do while sorting. Here we’ve got Bubble sort Java realisation:

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array  
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

The result of Bubble sort Java algorithm work:

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

How efficient is bubble sort?

Bubble sort is one of the easiest algorithms to implement but it isn’t efficient. It requires a pair of nested loops. Even in an optimized version of algorithm in the worst case (each element of the data set is in reverse order to the desired one) the outer loop iterates once for each of the n elements of the data set. The inner loop iterates n times the for the first time, (n-1) for the second, and so on. Hence, to get all n, elements sorted, the loops need to be executed n*(n-1)/2 times. It calls O(n²) time complexity and means that algorithm does about 500 000 comparisons for 1000 elements of an array. However, bubble sort algorithm is pretty effective in memory usage (memory complexity is O(n)) and is really good for almost sorted small datasets.

So, you've learned how Bubble Sort works — swapping adjacent elements until the whole list is sorted. Simple, right? But now you might be wondering, "How efficient is this algorithm?" Great question! Let’s dive deeper into the time and space complexity of Bubble Sort and see how it stacks up against other sorting algorithms.

Time Complexity Analysis of Bubble Sort

Time complexity tells us how the runtime of an algorithm scales with input size. Let’s break it down:

Best-Case Scenario (O(n))

Imagine the array is already sorted. Bubble Sort still has to make a pass through the list to check that no swaps are needed. But with an optimized version that stops early if no swaps occur, this takes just O(n) time.

Average-Case Scenario (O(n²))

For a randomly ordered array, Bubble Sort has to compare and swap elements multiple times, resulting in a time complexity of O(n²). This happens because for each element, it compares with every other element.

Worst-Case Scenario (O(n²))

In the worst case—when the array is sorted in reverse order—Bubble Sort must make the maximum number of swaps. This also results in O(n²) complexity.

Summary Table of Time Complexity

Space Complexity Analysis of Bubble Sort

Now, let’s talk about space. How much extra memory does Bubble Sort use?

The answer: O(1) auxiliary space. Bubble Sort only swaps elements in place and doesn’t need any additional arrays or data structures. Neat, right?

Why is Bubble Sort O(1) in Space?

• It uses only a few extra variables for swapping.
• No extra arrays or objects are created.

This makes Bubble Sort memory-efficient, though not time-efficient. So, while it won’t eat up your RAM, it might make your processor sweat!

Comparing Bubble Sort with Other Sorting Algorithms

Bubble Sort isn’t the only sorting game in town. Let’s compare it with other popular sorting algorithms to see how it holds up.

Bubble Sort vs. Insertion Sort

• Best Case: Both Bubble Sort and Insertion Sort have O(n) when optimized.
• Average/Worst Case: Both are O(n²), but Insertion Sort often performs better because it makes fewer swaps.

Bubble Sort vs. Merge Sort

• Time Complexity: Merge Sort is consistently O(n log n), making it much faster than Bubble Sort.
• Space Complexity: Merge Sort uses O(n) extra space, while Bubble Sort uses O(1).

Bubble Sort vs. Quick Sort

• Best/Average Case: Quick Sort runs in O(n log n).
• Worst Case: Quick Sort can degrade to O(n²) if poorly implemented, but it’s still faster than Bubble Sort in most cases.

Summary Comparison Table

When Should You Use Bubble Sort?

Given its performance, you’re probably thinking, "Is Bubble Sort even useful?" Well, yes and no.

When to Use Bubble Sort:

• When working with very small datasets.
• In educational contexts for learning how sorting algorithms work.
• When simplicity is more important than performance.

When to Avoid Bubble Sort:

• For large datasets—use Merge Sort, Quick Sort, or built-in Java sort methods instead.
• When performance is critical.