Bubble Sort

Bubble Sort is a simple sorting algorithm that 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 list is sorted.

Complexity Analysis

Best Case

O(n)

Average Case

O(n²)

Worst Case

O(n²)

Space Complexity

O(1)

function bubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

How Bubble Sort Works

Bubble Sort works by repeatedly swapping adjacent elements if they are in the wrong order. This process continues until no more swaps are needed, indicating that the array is sorted.

Algorithm Steps:

  1. Start with the first element (index 0)
  2. Compare it with the next element (index 1)
  3. If the current element is greater than the next element, swap them
  4. Move to the next pair and repeat the comparison and swap
  5. Continue until you reach the end of the array
  6. Repeat the entire process for the remaining unsorted portion
  7. Stop when no swaps are made in a complete pass

Characteristics:

  • Stable: Maintains the relative order of equal elements
  • In-place: Requires only constant extra space O(1)
  • Adaptive: Performs better on partially sorted arrays
  • Simple: Easy to understand and implement