Bubble Sort

Tags

Bubble Sort

Category

Sorting

Difficulty

Easy

Problem Statement

Implement the bubble sort algorithm to sort an array of integers in ascending order. Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the array is sorted.

Intuition

On each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array. After k passes, the last k elements are in their final positions. If a complete pass makes no swaps, the array is sorted and we can stop early.

Approach

  1. Initialize a boolean isSorted to false.
  2. While not sorted:
    • Set isSorted to true at the start of each pass.
    • Iterate from index 0 to the current unsorted boundary.
    • If array[i] > array[i + 1], swap them and set isSorted to false.
    • Shrink the unsorted boundary by one after each pass (the last element is now in place).
  3. Return the sorted array.

Pseudocode

function bubbleSort(array):
    isSorted = false
    counter = 0
    while not isSorted:
        isSorted = true
        for i from 0 to length(array) - 2 - counter:
            if array[i] > array[i + 1]:
                swap(array[i], array[i + 1])
                isSorted = false
        counter += 1
    return array

Time & Space Complexity

  • Time: O(n^2) worst and average case. O(n) best case when the array is already sorted (one pass with no swaps).
  • Space: O(1) — Sorting is done in-place.

Key Insights

  • Bubble sort is one of the simplest sorting algorithms to understand and implement.
  • The early termination optimization (stopping when no swaps occur) gives O(n) best-case performance.
  • After each pass, one more element is guaranteed to be in its final position, so the inner loop can shrink.
  • Despite its simplicity, bubble sort is inefficient for large datasets compared to O(n log n) algorithms.

Edge Cases

  • Empty array — already sorted, return immediately.
  • Single-element array — already sorted.
  • Already sorted array — one pass with no swaps, O(n) time.
  • Reverse-sorted array — worst case, requires n-1 passes.
  • Array with duplicate values — stable sort, equal elements maintain relative order.

Linked mentions