Bubble Sort

Repeatedly compares neighbours and swaps them when out of order, so the largest value "bubbles" to the end each pass. Educational gold, production rarely — O(n²).

Category: Sorting
Time complexity: O(n²)
Space complexity: O(1)

Pseudocode

procedure bubbleSort(A)
  for i ← 0 to n−2
    for j ← 0 to n−2−i
      if A[j] > A[j+1]
        swap A[j], A[j+1]
end procedure

Reference implementation

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] &gt; a[j + 1]:
                a[j], a[j+1] = a[j+1], a[j]

Open the interactive Bubble Sort visualisation →