Bubble Sort in Java
Problem
Bubble sort repeatedly steps through the array, swapping adjacent elements that are out of order, so the largest unsorted value 'bubbles up' to its correct position on each pass.
Given an array of integers, sort it in ascending order using bubble sort.
Java Program
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {9, 3, 7, 1, 8};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) { // shrinks by i each pass, skipping the already-sorted tail
if (arr[j] > arr[j + 1]) { // out of order, swap them
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}Output
Core Logic
Repeatedly sweeping through the array and swapping any adjacent pair that's out of order pushes the largest remaining value to the end on every pass.
- 1The outer loop runs
arr.length - 1passes over the array. - 2The inner loop compares each element against its neighbor, from index
0up toarr.length - 2 - i, shrinking by one each pass. - 3
if (arr[j] > arr[j + 1])checks whether the pair is out of order, swapping them with a temp variable if so. - 4After each full outer-loop pass, the largest unsorted value has 'bubbled up' to its correct final position at the end of the unsorted section.
[9, 3, 7, 1, 8], the first pass bubbles 9 all the way to the last index; the next pass settles 8 into place, and so on until the array is fully sorted.Key Point: Shrinking the inner loop's range by i each pass skips re-comparing the elements already bubbled into place at the end — they're already sorted and don't need re-checking.
Why: The nested loops compare roughly n²/2 pairs in the worst case, and the swaps happen in place using only a temp variable.
Key Concepts
Approach 2: Optimized (Early Exit)
import java.util.Arrays;
public class BubbleSortOptimized {
public static void main(String[] args) {
int[] arr = {9, 3, 7, 1, 8};
for (int i = 0; i < arr.length - 1; i++) {
boolean swapped = false; // tracks whether this pass made any changes
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) { // out of order, swap them
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // no swaps this pass means the array is already sorted
}
System.out.println(Arrays.toString(arr));
}
}
Output
Core Logic
Tracking whether any swap happened during a pass lets the algorithm stop early once the array is already sorted, instead of always running every planned pass.
- 1A boolean
swappedflag is reset tofalseat the start of every outer-loop pass. - 2Whenever the inner loop performs a swap,
swappedis set totrue. - 3After the inner loop finishes,
if (!swapped) break;exits the outer loop immediately if no swap happened during that whole pass. - 4No swaps in a full pass means every remaining pair is already in order, so there's nothing left to sort.
[1, 3, 7, 8, 9] were already sorted going in, the very first pass would find no out-of-order pairs, leave swapped as false, and exit immediately instead of running four more passes.Key Point: This doesn't change the worst-case O(n²) time — a fully reverse-sorted array still needs every pass — but it brings the best case (an already-sorted array) down to O(n), a single pass that finds nothing to swap.
Why: The worst case still compares roughly n²/2 pairs, but an already-sorted array exits after just one O(n) pass instead of running every planned pass.