[정렬] 버블 Bubble Sort

버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 데이터를 비교하면서, 큰 값을 오른쪽으로 하나씩 밀어내며 정렬하는 방식이다.

정렬이 끝날수록 가장 큰 값들이 차례로 오른쪽 끝에 쌓이게 된다.

시간 복잡도

• $O(n²)$

정렬 로직

1. 첫 번째 값과 두 번째 값을 비교해 왼쪽 값이 더 크면 두 값을 교환한다.
2. 한 칸 오른쪽으로 이동하며 같은 과정을 반복한다.
3. 한 바퀴를 돌면 가장 큰 값이 맨 오른쪽에 정렬된다.
4. 오른쪽 끝(정렬 완료된 구간)을 제외하고 위 과정을 반복한다.

코드 예시 (Java)

public static void solution(int length, int[] arr) {
    // 밀어주는 반복문
    for (int i = 0; i < length - 1; i++) {
        System.out.println((i + 1) + " " + Arrays.toString(arr));
        // 각 값 비교 후 swap 반복
        for (int j = 0; j < length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) { // 오름차순
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

핵심 포인트

• 이중 반복문 구조 두 번째 반복문이 실제 비교와 교환(swap)을 담당한다. length - 1 - i는 이미 정렬된 구간을 제외하기 위한 조건이다.
  
• 비교 조건
  • arr[j] > arr[j + 1] → 오름차순
  • arr[j] < arr[j + 1] → 내림차순

버블 정렬은 구현이 간단하지만, 데이터 개수가 많을수록 비효율적이다.

그래도 정렬의 기본 원리를 이해하기에 좋은 알고리즘이다.