Bubble Sort

Sort an integer array in ascending order using bubble sort. Bubble sort repeatedly walks the array, comparing each adjacent pair and swapping the two when…

Sort an integer array in ascending order using bubble sort. Bubble sort repeatedly walks the array, comparing each adjacent pair and swapping the two when they are out of order. After each pass the largest remaining value "bubbles" up to its correct position at the tail, so the sorted region grows from the right. The classic version runs a fixed n − 1 passes. The optimised version keeps a swapped flag and stops the moment a full pass makes no swaps, which makes already-sorted input finish in a single linear pass.

- `1 <= n <= 10^3` - `-10^6 <= arr[i] <= 10^6` - Elements may be negative, zero, or positive, and may repeat. - Sorting is in place and uses O(1) extra space. - Output is the array in ascending order.

Example 1: input arr = [5, 2, 8, 1, 9]; output [1, 2, 5, 8, 9]. Each pass bubbles the largest unsorted value to the tail. After pass 1 the value 9 is settled; later passes settle 8, 5, 2 until the array is fully ordered.

Example 2: input arr = [1, 2, 3, 4]; output [1, 2, 3, 4]. The array is already sorted. The early-exit version makes one full pass, sees zero swaps, and stops immediately.

Example 3: input arr = [7]; output [7]. A single element has no adjacent pair to compare, so no swap fires and the array is returned unchanged.

Category: Sorting & Searching. Topic: sorting-searching. Difficulty: Easy. Patterns: linear-scan.