Bubble Sort: A Classic Sorting Algorithm

Sorting is a fundamental concept in computer science, and Bubble Sort is one of the simplest and most intuitive sorting algorithms. Despite its simplicity, Bubble Sort provides valuable insights into the basics of sorting and algorithm optimization. In this post, I’ll delve into how Bubble Sort works, provide a detailed implementation, and analyze its time and space complexity.

How Bubble Sort Works

Bubble Sort is a comparison-based sorting algorithm that repeatedly steps through the list to be sorted, compares adjacent items, and swaps them if they are in the wrong order. The algorithm continues to do this until the list is sorted.

Key Concepts

1. Adjacent Comparison: Bubble Sort compares each pair of adjacent elements and swaps them if necessary.
2. Passes: After each pass through the list, the next largest element “bubbles up” to its correct position.
3. Early Termination: If no swaps are made during a pass, the algorithm terminates early, indicating that the list is already sorted.

For a visual representation of Bubble Sort in action, check out this video.

Implementation

Here’s a TypeScript implementation of Bubble Sort:

export const bubbleSort = (array: number[]): number[] => {
  for (let j = 0; j < array.length; j++) {
    let swapped = false;
    for (let i = 0; i < array.length - 1 - j; i++) {
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        swapped = true;
      }
    }
    // If no elements were swapped in the inner loop, the array is sorted
    if (!swapped) {
      break;
    }
  }
  return array;
};

Disclaimer: Please note that the following implementation modifies the input array directly to sort the elements in place. If you need to retain the original array, consider creating a copy before applying the sort.

Explanation of the Implementation

1. Outer Loop: The outer loop runs n times, where n is the length of the array. Each iteration ensures that the largest unsorted element is moved to its correct position.
2. Inner Loop: The inner loop performs the comparisons and swaps. The range of the inner loop reduces with each outer loop iteration because the largest elements are placed in their final positions.
3. Swapped Flag: The swapped flag helps in optimizing the algorithm. If no elements were swapped during a pass, the algorithm breaks out of the loop early, indicating that the array is already sorted.

Time and Space Complexity

Time Complexity

• Worst-case: O(n²) => This occurs when the array is in reverse order. Each element needs to be compared with every other element.
• Best-case: O(n) => This occurs when the array is already sorted. The algorithm terminates early after one pass.
• Average-case: O(n²) => On average, Bubble Sort performs O(n²) comparisons and swaps.

Space Complexity

• Space Complexity: O(1) => Bubble Sort is an in-place sorting algorithm, meaning it only requires a constant amount of additional memory space regardless of the input size.

Further Reading

For more insights into sorting algorithms, check out our detailed posts on other classic algorithms:

• Selection Sort: Learn how this algorithm finds the minimum element and places it in its correct position.
• Insertion Sort: Explore how this algorithm builds the final sorted array one item at a time.
• Quick Sort: Discover how Quick Sort uses a divide-and-conquer approach to sort efficiently.
• Merge Sort: Understand how Merge Sort divides the array into halves and merges them to produce a sorted result.

Conclusion

Bubble Sort is an excellent algorithm for understanding basic sorting principles. While it is not suitable for large datasets due to its O(n²) time complexity, it provides a clear example of how sorting algorithms can be optimized with early termination.

Whether you’re a beginner or just refreshing your knowledge, Bubble Sort is a great starting point for learning about sorting algorithms.