Sort an array by repeatedly swapping adjacent out-of-order elements, bubbling the largest to the end each pass.
Nested loops compare neighbors and swap when out of order; after pass i the last i elements are sorted. An "did we swap?" flag lets it exit early on an already-sorted array (best case O(n)). Average/worst case O(n^2) — a teaching sort, not a production one.
public static void bubbleSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
boolean swapped = false;
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = true; }
}
if (!swapped) break;
}
}function bubbleSort(a) {
for (let i = 0; i < a.length - 1; i++) {
let swapped = false;
for (let j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) { [a[j], a[j + 1]] = [a[j + 1], a[j]]; swapped = true; }
}
if (!swapped) break;
}
return a;
}def bubble_sort(a):
for i in range(len(a) - 1):
swapped = False
for j in range(len(a) - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped:
break
return aRarely used in production, but bubble sort is the canonical way interviewers check that you understand swaps, nested loops, and complexity analysis.
What optimization makes bubble sort O(n) on an already-sorted array?