Skip to main content

​
Overview

Bubble Sort is one of the simplest sorting algorithms to understand and implement. It works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The algorithm gets its name because smaller elements “bubble” to the top of the list.

​
Complexity

  • Time Complexity: O(n²) in all cases (best, average, and worst)
  • Space Complexity: O(1) - sorts in-place
  • Stable: Yes - maintains relative order of equal elements

​
Implementation

Here’s the actual implementation from the Sorting Algorithms Visualiser: 
void BubbleSort(std::vector<int>& nums) {
	for (int i = 0; i < nums.size(); i++) {
		for (int j = 0; j < nums.size() - i - 1; j++) {
			if (nums[j] > nums[j + 1])
				swapNums(&nums[j], &nums[j + 1]);
			HighlightRectangles(j, j+1, -1);
			std::this_thread::sleep_for(std::chrono::nanoseconds(SORT_DELAY));
		}
	}
	Verify(nums);
	return;
}

​
How It Works

  1. Outer Loop: Iterates through the entire array n times
  2. Inner Loop: Compares adjacent pairs from the start to n - i - 1
    • The -i optimization exists because after each pass, the largest element is guaranteed to be in its final position
  3. Comparison: If nums[j] > nums[j + 1], swap them
  4. Verification: After sorting completes, the Verify() function highlights each element to confirm the array is sorted

​
Step-by-Step Example

For the array [5, 3, 8, 4, 2]: Pass 1:
  • Compare 5 & 3 → Swap → [3, 5, 8, 4, 2]
  • Compare 5 & 8 → No swap
  • Compare 8 & 4 → Swap → [3, 5, 4, 8, 2]
  • Compare 8 & 2 → Swap → [3, 5, 4, 2, 8] (8 is now in final position)
Pass 2:
  • Compare 3 & 5 → No swap
  • Compare 5 & 4 → Swap → [3, 4, 5, 2, 8]
  • Compare 5 & 2 → Swap → [3, 4, 2, 5, 8] (5 is now in final position)
…continues until fully sorted.

​
Watch It in Action

When running the visualiser, you’ll see:
  • Red highlight (highlight1): Current element at position j
  • Green highlight (highlight2): Adjacent element at position j+1
  • Blue highlight: Used during the verification phase
The algorithm compares and potentially swaps these two adjacent elements on each step. You’ll notice that after each complete pass through the array, the largest unsorted element “bubbles up” to its final position at the end.
The visualization highlights show exactly which two elements are being compared at each step (lines 91-92 in the implementation).

​
Best Use Cases

  • Educational purposes: Excellent for teaching sorting concepts
  • Small datasets: Acceptable performance for very small arrays (< 10 elements)
  • Nearly sorted data: Can be optimized with an early exit flag
  • Simple requirements: When code simplicity is more important than performance
Bubble Sort is inefficient for large datasets. Consider using Quick Sort, Merge Sort, or built-in sorting functions for production code.

​
Advantages

✓ Simple to understand and implement ✓ Requires no additional memory (in-place sorting) ✓ Stable sorting algorithm ✓ Can detect if the list is already sorted (with optimization)

​
Disadvantages

✗ Very slow for large datasets (O(n²) comparisons) ✗ Many unnecessary comparisons even if nearly sorted ✗ Generally outperformed by insertion sort for small arrays

Build docs developers (and LLMs) love

Get started for freeTalk to us