Sorting - Bubble Sort

Implement the Bubble Sort algorithm. Repeatedly step through the list, compare adjacent elements, and swap them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Input: [64, 34, 25, 12, 22, 11, 90] → Output: [11, 12, 22, 25, 34, 64, 90]

Input: [5, 1, 4, 2, 8] → Output: [1, 2, 4, 5, 8]

In each pass, compare adjacent pairs and swap if needed. The largest unsorted element "bubbles up" to its correct position. Optimize by stopping early if no swaps occur in a pass.

Outer loop runs n-1 times (n = array length).
Inner loop compares arr[j] and arr[j+1] for j from 0 to n-i-2.
If arr[j] > arr[j+1], swap them.
Use a swapped flag to break early if the array is already sorted.

class BubbleSort { public void sort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { boolean swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; swapped = true; } } if (!swapped) break; } } }

Time Complexity: O(N^2) worst/average, O(N) best (already sorted)
Space Complexity: O(1) in-place