Sorting an Array: Bubble Sort in Java
Sorting is an essential operation in programming, used to arrange elements in ascending or
descending order. One of the simplest sorting algorithms is Bubble Sort.
What is Bubble Sort?
Bubble Sort is a simple sorting algorithm that repeatedly steps through the array, compares
adjacent elements, and swaps them if they are in the wrong order. This process continues until
the entire array is sorted.
Working of Bubble Sort
1. Start at the beginning of the array.
2. Compare adjacent elements.
3. If the first element is greater than the second, swap them.
4. Move to the next pair of elements and repeat the process.
5. After each pass, the largest element moves to its correct position.
6. Repeat the passes until the array is sorted.
Bubble Sort Implementation in Java
Basic Implementation
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};
bubbleSort(arr);
System.out.println("Sorted Array: " + Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
Explanation
The outer loop runs n-1 times.
The inner loop runs fewer times in each pass, since the largest element is placed at the
end.
Swapping occurs whenever an adjacent element is out of order.
Optimized Bubble Sort (With Early Exit)
If no swaps occur during a pass, the array is already sorted, so we can terminate early.
import java.util.Arrays;
public class OptimizedBubbleSort {
public static void main(String[] args) {
int[] arr = {2, 3, 4, 5, 6}; // Already sorted
bubbleSort(arr);
System.out.println("Sorted Array: " + Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) { // If no swaps occurred, break early
break;
}
}
}
}
Why Optimize?
The early exit condition improves performance for nearly sorted arrays.
Reduces unnecessary iterations when no swaps occur.
Time Complexity Analysis
Case Complexity
Best Case (Already Sorted) O(n) (Optimized)
Average Case O(n²)
Worst Case (Reversed Order) O(n²)
Best case: The optimized version stops in one pass if the array is already sorted.
Worst case: Every element is out of order, requiring maximum swaps.
Advantages & Disadvantages of Bubble Sort
✅ Advantages
Simple to understand and implement.
Works well for small datasets.
Can be optimized with an early exit condition.
❌ Disadvantages
Inefficient for large datasets due to O(n²) complexity.
Slower compared to advanced sorting algorithms like Quick Sort and Merge Sort.
Conclusion
Bubble Sort is a fundamental sorting algorithm, ideal for learning but not for large-scale
applications due to its inefficiency. However, understanding Bubble Sort helps in grasping more
complex sorting techniques like Quick Sort and Merge Sort.
