Bubble Sort

How it works

Bubble Sort iterates through the array repeatedly, comparing each pair of adjacent elements and swapping them when they are out of order. After the first pass the largest element is guaranteed to sit at the end; after the second pass the two largest are in place, and so on.

For an array of length n the algorithm performs up to n-1 passes. The optimized variant tracks whether any swap happened during a pass — if none did, the array is already sorted and the loop exits early, giving O(n) behaviour on sorted input.

Implementation

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
}

def bubble_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

void bubbleSort(vector<int>& arr) {
  for (int i = 0; i < arr.size()-1; i++) {
    for (int j = 0; j < arr.size()-1-i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j+1]);
      }
    }
  }
}

void BubbleSort(int[] arr) {
  for (int i = 0; i < arr.Length - 1; i++) {
    for (int j = 0; j < arr.Length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        (arr[j], arr[j+1]) = (arr[j+1], arr[j]);
      }
    }
  }
}

void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        int tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
  }
}

Advantages

• Trivial to implement — a handful of lines, no recursion, no auxiliary structures.
• Stable: equal elements preserve their original relative order.
• In-place: only O(1) extra memory beyond the input array.
• Detects already-sorted input in O(n) when the early-exit check is enabled.

Disadvantages

• Average and worst-case O(n^2) — impractical beyond a few hundred elements.
• Performs many more swaps than Selection or Insertion Sort on the same input.
• Poor cache behaviour at scale due to the long repeated sweep.

When to use it

Almost never in production. Use it as a teaching example, a benchmark baseline, or when the input is guaranteed tiny and nearly sorted. For real work reach for Insertion Sort on small inputs or Tim Sort for general-purpose sorting.