Understanding Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.

How it works

1. First Pass: We start from the first element and compare it with the second. If the first element is greater, we swap them. We then compare the second and third, swapping if necessary. This process continues to the end of the array. At the end of this pass, the largest element "bubbles up" to the last position.
2. Subsequent Passes: We repeat the process for the remaining elements (excluding the last element which is already sorted).
3. Termination: The algorithm stops when no swaps are made in a complete pass.

Optimization

The algorithm can be optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time. Additionally, we can introduce a swapped boolean flag to break out of the loop early if the array becomes sorted before all passes are complete.

Mathematical Complexities

• Best Case Complexity O(N): Occurs when the array is already sorted.
• Worst & Average Case Complexity O(N²): Occurs when the array is reverse sorted.
• Space Complexity O(1): In-place sorting algorithm.

💡 Important Note: Despite its inefficiency, Bubble Sort is stable and requires zero additional memory, making it a common educational tool to introduce algorithmic thinking.