버블 정렬(Bubble Sort)

🫧 거품처럼 숫자가 떠오르는, 버블 정렬(Bubble Sort)

데이터를 순서대로 나열하는 정렬 알고리즘 중 가장 기초적이면서 직관적인 버블 정렬(Bubble Sort)에 대해 공부한 내용을 정리해 보았습니다!!

---

🧠 버블 정렬이란?

버블 정렬은 인접한 두 원소를 비교하며 조건에 맞지 않을 경우 자리를 교체하는 방식이예요.

마치 여러 사람이 줄을 서 있을 때,
맨 앞사람부터 시작해 오직 바로 옆 사람과만 키를 비교하며 더 큰 사람이 계속 뒤로 이동하는 밀어내기 방식과 같습니다.

🎨 그림으로 보는 정렬 원리

버블 정렬의 핵심은 가장 큰 값을 뒤로 밀어내는 것!!

💻 자바(Java) 구현 및 최적화

버블 정렬은 구현이 간단하지만, 기본적으로 $O(n^2)$의 시간 복잡도를 가집니다.
아래 코드는 이미 정렬이 완료된 경우 불필요한 반복을 피하도록 swapped 변수를 활용해 최적화한 버전입니다😃

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {

        // 정렬할 데이터 배열
        int[] data = {6, 3, 8, 5, 7, 9, 2};
        int n = data.length;

        // 바깥쪽 루프: 각 회전(Pass)마다 가장 큰 값이 뒤로 확정됨
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false; // 자리 교환 발생 여부 확인

            // 안쪽 루프: 인접한 두 숫자를 비교
            // 뒤쪽 i개는 이미 정렬되었으므로 비교 범위에서 제외 (n - 1 - i)
            for (int j = 0; j < n - 1 - i; j++) {

                // 앞의 숫자가 더 크면 교환(Swap)
                if (data[j] > data[j + 1]) {
                    int tmp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = tmp;

                    swapped = true; // 교환이 발생했음을 기록
                }
            }

            // 만약 이번 회전에서 교환이 단 한 번도 없었다면? 
            // 이미 정렬이 완료된 상태이므로 루프를 즉시 종료(Early Exit)
            if (!swapped) break;
        }

        // 결과 확인
        System.out.println("정렬 결과: " + Arrays.toString(data));
    }
}

💡 시간 복잡도(Time Complexity)란?

컴퓨터가 문제를 해결하는 데 걸리는 시간을 실제 '초' 단위가 아니라, 데이터의 개수 n 에 따른 연산 횟수로 나타낸 것입니다.
하드웨어 성능과 관계없이 알고리즘의 효율성을 객관적으로 판단하는 기준이 됩니다. 버블 정렬의 복잡도: \( O(n^2) \) 버블 정렬은 중첩된 반복문을 사용하기 때문에 데이터가 \( n \)개일 때 약 \( n^2 \)번의 비교 연산을 수행해요.
예를 들어 데이터가 10배 늘어나면 연산 횟수는 100배로 급격히 증가하게 됩니다.

---

📝 마무리

구분	내용
시간 복잡도	최악의 경우 $O(n^2)$, 최적화 시 $O(n)$
장점	구현이 정말 쉽고 직관적. 추가적인 메모리 공간도 거의 필요 없음.
단점	데이터가 많아질수록 비교 횟수가 너무 많아져서 성능이 떨어지는 편

이번 정리를 통해 버블 정렬의 동작 원리뿐만 아니라, 시간 복잡도라는 중요한 개념까지 구체적으로 이해할 수 있었어요.
단순한 알고리즘이지만 최적화 과정을 고민해 보는 것만으로도 공부가 많이 되는 시간이었습니다. 😉