Bubble Sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. It is named for the way smaller elements "bubble" to the top of the list.

Basic Implementation

function bubbleSort(arr: number[]): number[] {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      // Compare adjacent elements
      if (arr[j] > arr[j + 1]) {
        // Swap them if they are in the wrong order
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

How Bubble Sort Works

• The algorithm compares each pair of adjacent elements in the array and swaps them if they are in the wrong order.

• This process is repeated for each element in the array, and the largest unsorted element "bubbles up" to its correct position at the end of the array.

• The algorithm can be optimized by adding a flag to check whether any swaps were made in a pass. If no swaps are made, the array is already sorted, and the algorithm can terminate early.

Time Complexity

The time complexity of Bubble Sort is O(n^2) in the worst and average cases, where 'n' is the number of elements in the array. The best-case time complexity is O(n) when the array is already sorted.

Space Complexity

Bubble Sort has a space complexity of O(1) because it only requires a constant amount of additional space for temporary variables.

When to Use Bubble Sort

Bubble Sort is a simple algorithm suitable for small datasets or nearly sorted datasets. However, due to its quadratic time complexity, it is not efficient for large datasets. More advanced sorting algorithms like QuickSort or MergeSort are generally preferred for larger datasets.

Conclusion

Bubble Sort is a fundamental sorting algorithm that provides a clear illustration of the basic principles of sorting. While it's not the most efficient sorting algorithm for large datasets, understanding how it works can serve as a foundation for understanding more complex sorting algorithms.