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.




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(n2) 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
Scenario | Time Complexity |
---|---|
Best Case (Already Sorted) | O(n) |
Average Case | O(n²) |
Worst Case (Reverse Order) | O(n²) |
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
Algorithm | Best Case | Average Case | Worst Case | Space Complexity |
---|---|---|---|---|
Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
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.
GO TO FULL VERSION