Sorting

Bubble Sort

A simple comparison-based sorting algorithm that repeatedly swaps adjacent out-of-order elements.

What is Bubble Sort?

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. The pass through the list is repeated until the list is sorted, bubbling the largest unsorted elements to their correct positions at the end of each pass.

Key Characteristics:

  • Stable sort: maintains relative order of equal keys.
  • In-place sort: O(1) auxiliary memory.
  • Simple implementation but inefficient for large datasets.
  • Optimizable by stopping early if a pass completes without any swaps.

Complexity Analysis

Avg Time Complexity: O(N^2) average and worst case
Space Complexity: O(1) in-place storage
Best Case: O(N) (pre-sorted array with early exit check)
Worst Case: O(N^2) (reverse sorted array)

How it Works Step-by-Step

  1. Iterate Passes: Loop from i=0 to N-1 for passes.
  2. Compare Adjacent: Loop j from 0 to N-i-2. Compare array[j] and array[j+1].
  3. Swap: If array[j] > array[j+1], swap their positions. Set swapped = true.
  4. Optimization Check: If a pass finishes with swapped == false, the array is sorted; exit early.

Code Implementation

Worked Trace Example

Sorting [5, 1, 4, 2]:
1. Pass 1: Compare 5,1 (swap) -> [1, 5, 4, 2]. Compare 5,4 (swap) -> [1, 4, 5, 2]. Compare 5,2 (swap) -> [1, 4, 2, 5]. Max element 5 bubbled to end.
2. Pass 2: Compare 1,4 (no swap) -> [1, 4, 2, 5]. Compare 4,2 (swap) -> [1, 2, 4, 5]. Compare 4,5 (no swap) -> [1, 2, 4, 5].
3. Pass 3: No swaps occur. Exit early.
Result: Sorted array [1, 2, 4, 5].

Ready to Understand Bubble Sort Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Bubble Sort Visualizer →