Bubble Sort
Bubble sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. It gets its name because smaller elements "bubble" to the top of the list with each iteration.
How Bubble Sort Works
Bubble sort works by making multiple passes through an array. On each pass, it compares each pair of adjacent elements and swaps them if they are in the wrong order. After the first pass, the largest element is guaranteed to be at the end of the array. After the second pass, the second-largest is in place, and so on.
Step-by-step process:
- Start at the beginning: Begin with the first element in the array. Compare it with the next element.
- Compare adjacent elements: If the current element is greater than the next element, swap them. Otherwise, move on.
- Continue through the array: Repeat this comparison for every adjacent pair until the end of the array. This completes one "pass."
- Largest element bubbles up: After each pass, the largest unsorted element is now in its correct position at the end of the unsorted portion.
- Repeat: Continue making passes through the array, each time ignoring the already-sorted elements at the end.
- Early exit optimization: If a complete pass is made with no swaps, the array is already sorted and the algorithm can terminate early. This optimization makes the best-case time complexity O(n) for an already-sorted array.
While bubble sort is easy to understand and implement, it is not efficient for large datasets. Its O(n²) average and worst-case time complexity makes it impractical compared to algorithms like merge sort or quicksort for large arrays. However, its simplicity makes it an excellent teaching tool for understanding sorting algorithms.
Interactive Visualization
Watch how bubble sort compares and swaps adjacent elements pass by pass. Yellow bars indicate the pair being compared, orange bars indicate a swap, and green bars are in their final sorted position.
Code Implementation
Below is an optimized bubble sort implementation in three languages. The optimization includes an early exit flag: if no swaps occur during a pass, the array is already sorted and we can stop immediately.
def bubble_sort(arr):
"""Optimized bubble sort with early exit."""
n = len(arr)
for i in range(n - 1):
swapped = False
# Last i elements are already in place
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# If no swaps occurred, array is sorted
if not swapped:
break
return arr
# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90, 45]
print("Unsorted:", numbers)
print("Sorted: ", bubble_sort(numbers))
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
// Last i elements are already in place
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no swaps occurred, array is sorted
if (!swapped) break;
}
}
public static void main(String[] args) {
int[] numbers = {64, 34, 25, 12, 22, 11, 90, 45};
System.out.print("Unsorted: ");
printArray(numbers);
bubbleSort(numbers);
System.out.print("Sorted: ");
printArray(numbers);
}
private static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) System.out.print(", ");
}
System.out.println();
}
}
#include <iostream>
#include <vector>
using namespace std;
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
// Last i elements are already in place
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// If no swaps occurred, array is sorted
if (!swapped) break;
}
}
void printArray(const vector<int>& arr) {
for (int i = 0; i < arr.size(); i++) {
cout << arr[i];
if (i < arr.size() - 1) cout << ", ";
}
cout << endl;
}
int main() {
vector<int> numbers = {64, 34, 25, 12, 22, 11, 90, 45};
cout << "Unsorted: ";
printArray(numbers);
bubbleSort(numbers);
cout << "Sorted: ";
printArray(numbers);
return 0;
}
Complexity Analysis
Bubble sort's performance depends on the initial order of the elements. The optimized version with the early-exit flag achieves O(n) in the best case when the array is already sorted, since only one pass with zero swaps is needed.
| Metric | Complexity | Notes |
|---|---|---|
| Best Case Time | O(n) | Array is already sorted (with early exit optimization) |
| Average Case Time | O(n²) | Elements are in random order |
| Worst Case Time | O(n²) | Array is sorted in reverse order |
| Space Complexity | O(1) | In-place sorting, only uses a temporary variable for swaps |
| Stable | Yes | Equal elements maintain their relative order |
Practice Problems
Strengthen your understanding of sorting by working through these problems. While bubble sort itself may not be the optimal solution, these problems will help you think about sorting concepts and when different approaches are appropriate.
Quiz
Test your understanding of bubble sort with these questions.
Q1. What is the worst-case time complexity of bubble sort?
Q2. What optimization can make bubble sort's best-case time complexity O(n)?
Q3. Is bubble sort a stable sorting algorithm?
Q4. After the first complete pass of bubble sort on the array [5, 3, 8, 1, 2], which element is guaranteed to be in its correct position?
Q5. How many passes does bubble sort need to completely sort the array [2, 1, 3, 4, 5] using the optimized version with early exit?