Bubble Sort

Explanation

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 no swaps are needed, which indicates that the list is sorted. Because it only uses comparisons to operate on elements, it is a comparison sort.

Example Use Case

Let's say you have the array [5, 1, 4, 2, 8]. Here's how Bubble Sort would sort it:

1. **First Pass:**
   - (5, 1) -> (1, 5) swaps, array becomes [1, 5, 4, 2, 8]
   - (5, 4) -> (4, 5) swaps, array becomes [1, 4, 5, 2, 8]
   - (5, 2) -> (2, 5) swaps, array becomes [1, 4, 2, 5, 8]
   - (5, 8) -> no swap, array remains [1, 4, 2, 5, 8]

2. **Second Pass:**
   - (1, 4) -> no swap, array remains [1, 4, 2, 5, 8]
   - (4, 2) -> (2, 4) swaps, array becomes [1, 2, 4, 5, 8]
   - (4, 5) -> no swap, array remains [1, 2, 4, 5, 8]
   - (5, 8) -> no swap, array remains [1, 2, 4, 5, 8]

3. **Third Pass:**
   - (1, 2) -> no swap, array remains [1, 2, 4, 5, 8]
   - (2, 4) -> no swap, array remains [1, 2, 4, 5, 8]
   - (4, 5) -> no swap, array remains [1, 2, 4, 5, 8]
   - (5, 8) -> no swap, array remains [1, 2, 4, 5, 8]

4. **Fourth Pass:**
   - (1, 2) -> no swap, array remains [1, 2, 4, 5, 8]
   - (2, 4) -> no swap, array remains [1, 2, 4, 5, 8]
   - (4, 5) -> no swap, array remains [1, 2, 4, 5, 8]
   - (5, 8) -> no swap, array remains [1, 2, 4, 5, 8]

Since no swaps occurred during the third pass, the algorithm knows the array is sorted and terminates.

Theoretical Deep Dive

Bubble Sort has a time complexity of O(n^2) in the average and worst cases, and O(n) in the best case (when the array is already sorted). This makes it inefficient for sorting large lists. Its space complexity is O(1) because it sorts the array in-place.