버블 정렬(Bubble Sort)

🔷  버블 정렬(Bubble Sort)란?

버블 정렬은 가장 단순한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교해서 크기가 잘못된 경우 서로 교환하는 방식으로 동작합니다. 이러한 과정을 반복하면서 가장 큰(또는 작은) 요소가 끝으로 "버블처럼" 올라가는 모습을 보입니다.

버블정렬

✅ 작동 방식

1. 배열의 첫 번째 요소부터 인접한 두 요소를 비교합니다.
2. 앞의 값이 뒤의 값보다 크면, 두 값을 서로 교환합니다.
3. 이 과정을 배열의 끝까지 반복합니다.
4. 첫 번째 반복이 끝나면 가장 큰 값이 마지막에 위치하게 됩니다.
5. 다음 반복에서는 마지막 요소를 제외하고 같은 과정을 반복합니다.
6. 배열이 정렬될 때까지 이 과정을 반복합니다.

✅ 시간 복잡도

• 최악(O): O(n²)
• 평균: O(n²)
• 최선(정렬된 경우): O(n) (최적화된 버블 정렬 사용 시)
• 공간 복잡도: O(1) (제자리 정렬, in-place)

public class BubbleSortExample {

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        // 외부 루프는 전체 패스를 반복
        for (int i = 0; i < n - 1; i++) {
            swapped = false; // 교환 여부를 추적

            // 내부 루프는 현재 패스에서 정렬
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 요소 교환
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;

                    swapped = true; // 교환 발생
                }
            }

            // 교환이 없었다면 배열은 이미 정렬된 상태
            if (!swapped) break;
        }
    }

    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 실행 메서드
    public static void main(String[] args) {
        int[] numbers = {5, 3, 8, 4, 2};

        System.out.println("정렬 전 배열:");
        printArray(numbers);

        bubbleSort(numbers);

        System.out.println("정렬 후 배열:");
        printArray(numbers);
    }
}

 

✅ 출력 결과

정렬 전 배열:
5 3 8 4 2 
정렬 후 배열:
2 3 4 5 8

 

요약 정리

• 버블 정렬은 개념이 간단해서 입문자에게 매우 좋습니다.
• 하지만 성능은 좋지 않기 때문에 작은 데이터에 적합합니다.
• Java 구현도 쉽고 직관적이므로 기본 정렬 알고리즘을 이해할 때 매우 유용하죠.

---