Bubble Sort

Repeatedly swaps adjacent elements if they are in wrong order until the largest values bubble to the end.

How it works

Bubble sort walks through the array from left to right, comparing each pair of adjacent elements. If the left value is bigger than the right one, they swap. By the end of the first pass the largest value has "bubbled" all the way to the last position.

Each following pass repeats the same walk over the remaining unsorted part, which shrinks by one element every time. If a whole pass finishes without a single swap, the array is already sorted and the algorithm stops early.

Implementations

function bubbleSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    let swapped = false;

    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
        swapped = true;
      }
    }

    if (!swapped) break;
  }

  return array;
}

def bubble_sort(array):
    a = list(array)
    n = len(a)

    for i in range(n - 1):
        swapped = False

        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True

        if not swapped:
            break

    return a

Complexity

Case	Time	When
Best	O(n)	Already sorted: one pass with no swaps
Average	O(n²)	Random order
Worst	O(n²)	Sorted in reverse