Bubble Sort

"Bubbling" the largest to the top

The simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. Small elements "bubble" to the top, while the largest elements sink to the bottom (the end of the array) in each pass.

Passes

Comparisons

Swaps

Press "Start Sorting" to begin

Unsorted

Checking

Swapping

Sorted

Speed

The Mechanics of Bubble Sort

Bubble Sort is often the first sorting algorithm taught because of its conceptual simplicity. It repeatedly compares adjacent elements and swaps them if they are in the wrong order.

The Optimization

A basic bubble sort always runs $O(n^2)$ times, even if the array is already sorted. The Optimized Bubble Sort includes a flag to check if any swap happened during an inner loop. If no swap occurs, the algorithm stops early, giving it a best-case time complexity of $O(n)$.

Properties

Stable: Mantains relative order of equal elements.
In-place: Only $O(1)$ extra space required.
Adaptive: Gains speed with partially sorted data.

When to Use?

Rarely used in production due to its poor performance on large datasets. However, it's efficient for arrays that are nearly sorted or for very small collections where the simplicity of the code yields low overhead.

Efficiency Stats

Worst-case Time$O(n^2)$

Average Time$O(n^2)$

Best-case (Opt.)$O(n)$

Space Complexity$O(1)$

Did you know?

"In each pass of bubble sort, at least one more element (the largest among unsorted) is placed at its correct position. That's why the inner loop range decreases by 1 ($n-i-1$) after every pass."

Logic

Pseudocode

JavaScript

1if (arr[j] > arr[j+1]) {
2  [arr[j], arr[j+1]] = 
3  [arr[j+1], arr[j]];
4  swapped = true;
5}

Recursive & Iterative Implementation

Python Implementation

Pseudocode

Python

1def bubble_sort(arr):
2    n = len(arr)
3    # Traverse through all array elements
4    for i in range(n):
5        swapped = False
6        # Last i elements are already in place
7        for j in range(0, n - i - 1):
8            if arr[j] > arr[j + 1]:
9                arr[j], arr[j + 1] = arr[j + 1], arr[j]
10                swapped = True
11        
12        # If no elements swapped, array is sorted
13        if not swapped:
14            break
15    return arr

JavaScript Implementation

Pseudocode

JavaScript

1function bubbleSort(arr) {
2  let n = arr.length;
3  let swapped;
4  
5  do {
6    swapped = false;
7    for (let i = 0; i < n - 1; i++) {
8      if (arr[i] > arr[i + 1]) {
9        // Swap elements
10        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
11        swapped = true;
12      }
13    }
14    // Optimization: The last element is sorted
15    n--;
16  } while (swapped);
17  
18  return arr;
19}

The Mechanics of Bubble Sort

Bubble Sort is often the first sorting algorithm taught because of its conceptual simplicity. It repeatedly compares adjacent elements and swaps them if they are in the wrong order.

The Optimization

Recursive & Iterative Implementation

Python Implementation

Pseudocode

Python

1def bubble_sort(arr):
2    n = len(arr)
3    # Traverse through all array elements
4    for i in range(n):
5        swapped = False
6        # Last i elements are already in place
7        for j in range(0, n - i - 1):
8            if arr[j] > arr[j + 1]:
9                arr[j], arr[j + 1] = arr[j + 1], arr[j]
10                swapped = True
11        
12        # If no elements swapped, array is sorted
13        if not swapped:
14            break
15    return arr

JavaScript Implementation

Pseudocode

JavaScript

1function bubbleSort(arr) {
2  let n = arr.length;
3  let swapped;
4  
5  do {
6    swapped = false;
7    for (let i = 0; i < n - 1; i++) {
8      if (arr[i] > arr[i + 1]) {
9        // Swap elements
10        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
11        swapped = true;
12      }
13    }
14    // Optimization: The last element is sorted
15    n--;
16  } while (swapped);
17  
18  return arr;
19}