거품 정렬 (Bubble Sort)

1. 개요

• 인접한 두 원소를 비교하여 필요한 경우 자리를 교환한다.
• 한 번의 사이클이 끝나면 가장 큰 원소가 맨 뒤로 간다. (오름차순 기준)
• 찾는 값이 거품처럼 나온다고 해서 거품 정렬이다.

---

2. 특징

• 구현이 간단하다.
• 교환하는 방식이기 때문에 추가적인 메모리를 사용하지 않는다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort)이다. => 중복된 값을 입력 순서와 동일하게 유지
• 시간복잡도: O(N^2)

---

3. 코드

import java.util.Arrays;

public class BubbleSortTest {

    public static void main(String[] args) {
        int[] arr = {3, 7, 2, 5, 1, 10};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                }
            }
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}