Bubble Sort

Time complexity: O(n²)

Space complexity: O(1)

Data type: Arrays

Visualization

Comparisons: 0

Reorders: 0

Delay: 1ms

Items: 50

Definition

Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until the list is sorted.

Constraints

  • Inefficient for large datasets due to O(n²) time complexity
  • Generally performs worse than insertion sort in practice
  • Adaptive version can optimize for nearly-sorted inputs
  • Mostly used for educational purposes rather than production

Step-by-step explanation

Arguments:

  • Array to be sorted - array
  • Current index in pass - i
  • Flag for early termination - swapped
  • Number of passes completed - passCount
  • Temporary variable for swaps - temp

Explanation:

  • Start at the beginning of the array
  • Compare each pair of adjacent elements:
    • If element at i is greater than element at i+1, swap them
  • Continue comparing and swapping to the end of the array
  • After each complete pass, the largest unsorted element "bubbles up" to its correct position
  • Repeat process for remaining unsorted portion of array
  • Optimization: Stop early if no swaps occurred in a pass (array is sorted)

Returns:

Returns nothing (sorts array in-place)
Modifies the original array instead of returning a new one
No explicit return value (void function in most implementations)

Example

1
#include <iostream>
2
#include <vector>
3


4
void bubbleSortIterative(std::vector<int>& arr) {
5
    int n = (int)arr.size();
6
    for (int i = 0; i < n - 1; ++i) {
7
        // After i-th pass, the last i elements are in correct position
8
        for (int j = 0; j < n - i - 1; ++j) {
9
            if (arr[j] > arr[j + 1]) {
10
                std::swap(arr[j], arr[j + 1]);
11
            }
12
        }
13
    }
14
}