버블 정렬

인접한 두 원소를 비교해 순서가 잘못됐으면 교환하며, 가장 큰 값을 뒤로 밀어내는 정렬입니다.

동작 과정

[5, 3, 8, 1, 2]

pass 1: 5↔3 → 3↔5 → 5↔8 → 8↔1 → 8↔2  → [3, 5, 1, 2, 8]
pass 2: 3↔5 → 5↔1 → 5↔2             → [3, 1, 2, 5, 8]
pass 3: 3↔1 → 3↔2                   → [1, 2, 3, 5, 8]
pass 4: 1↔2                         → [1, 2, 3, 5, 8] 완료

구현

void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

복잡도

• 안정 정렬 O
• in-place O

→ 정렬