# Bubble Sort

Source: https://wisconsin.twango.dev/fa24-cs300/u3-algorithms/sorting-and-search/sorting/bubble-sort

# Bubble Sort

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.

## Features
- [x] Stable sorting algorithm
- [x] In-place sorting algorithm

## Implementation

### Pseudocode

```text
procedure bubbleSort(A : list of sortable items)
    n = length(A)
    repeat
        swapped = false
        for i = 1 to n-1 inclusive do
            if A[i-1] > A[i] then
                swap(A[i-1], A[i])
                swapped = true
            end if
        end for
        n = n - 1
    until not swapped
end procedure
```

### Java

```java
public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    do {
        swapped = false;
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                int temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;
                swapped = true;
            }
        }
        n--;
    } while (swapped);
}
```

## Runtime Analysis
The displayed early-exit bubble sort takes $\Theta(N)$ time on an already sorted array and $\Theta(N^2)$ time in the worst case. Its swaps equal the number of inversions $K$, but comparisons are not generally $\Theta(N+K)$: an element near the end may move left only one position per pass.

### Best Case
The best case occurs when the array is already sorted. In this case, the algorithm makes a single pass through the array and does not perform any swaps. The time complexity is $\Omega(N)$.

### Worst Case
The worst case occurs when the array is sorted in reverse order. In this case, the algorithm makes $N-1$ passes through the array, performing $N-1$ swaps on the first pass, $N-2$ swaps on the second pass, and so on. The total number of inversion pairs, $K$ in a reverse-sorted array, is given by:

$$
K = (N-1) + (N-2) + \ldots + 1 = \frac{N(N-1)}{2}
$$

This results in a time complexity of $O(N^2)$.

## Source

The existing course note was retained and normalized during the merge.

Related: [[u3-algorithms/sorting-and-search/index|Topic index]].