Bubble Sort is the simplest sorting algorithm. It works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. Each pass bubbles the largest unsorted element to its correct position. An early-exit optimization gives it O(n) best-case performance on already-sorted input.
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
swapped = true;
}
}
if (!swapped) break;
}
}Bubble Sort makes repeated passes through the array. On each pass it compares adjacent pairs and swaps them when out of order. After pass i, the i largest elements are in their final positions at the end of the array.
If a full pass completes with no swaps, the array is already sorted. Tracking a swapped flag lets us break early, giving O(n) best-case performance on nearly-sorted data.
Worst case is a reverse-sorted array: O(n²) comparisons. Average case is also O(n²). Space is O(1) because sorting is done in-place with only a temp variable for swapping.
Bubble Sort is rarely used in production. It is best for teaching sorting fundamentals, for tiny arrays where simplicity beats performance, or as a baseline to compare against better algorithms.
What is the average-case time complexity of Bubble Sort?
Bubble Sort is:
What is the best-case time complexity of Bubble Sort (with early exit)?