Bubble Sort

Given an unsorted array of integers, sort it in ascending order using Bubble Sort. Modify the array in-place (O(1) extra space). Input: [5, 1, 4, 2, 8] → Output: [1, 2, 4, 5, 8]. Do not use built-in sort functions. Implement both iterative and recursive versions.

Bubble Sort repeatedly "bubbles" the largest unsorted element to its correct position by comparing adjacent pairs and swapping if they are in the wrong order. After each full pass through the array, the largest remaining element is guaranteed to be in its final position. This means each subsequent pass can skip the last element(s). The name "bubble" comes from how larger elements float to the end.

1. Outer loop: run from i = 0 to n-1 (n passes). 2. Inner loop: compare adjacent elements from j = 1 to n-i (each pass has one fewer element to check). 3. If arr[k] > arr[j], swap them. 4. After n passes, the array is sorted. 5. Recursive version: replace the outer loop with recursion — each recursive call represents one pass, with i incrementing.

- Forgetting to reduce the inner loop range with each pass (the last i elements are already sorted) - Not using a "swapped" flag for early termination — if no swaps occur in a pass, the array is already sorted - Confusing the indices in the recursive version, leading to incorrect or infinite recursion - Using Bubble Sort for large arrays in production — it is O(N^2) and impractical beyond ~10,000 elements

Bubble Sort is the simplest sorting algorithm to understand and implement but one of the least efficient. Its main value is educational: it introduces the concept of sorting through repeated comparisons and swaps. In practice, use algorithms like Merge Sort (O(N log N)) or Python's built-in Timsort. However, understanding Bubble Sort is essential before tackling more efficient algorithms.