버블 정렬 (Bubble Sort): 개념부터 실전 코딩까지 완벽 가이드

목차

1. 버블 정렬(Bubble Sort)이란? 용어, 개념, 특징

1.1 용어 및 정의

버블 정렬(Bubble Sort)은 가장 기초적인 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 교환하는 방식으로 정렬을 수행합니다. 정렬이 완료될 때까지 여러 번 배열을 순회하며 큰 값이 점차 뒤쪽으로 이동하는 방식이 거품이 떠오르는 모습과 유사하여 '버블 정렬'이라는 이름이 붙었습니다. 큰 값이 "거품"처럼 배열 끝으로 떠오르는 모습에서 이름이 유래했습니다.

1.2 주요 개념

• 비교 기반 정렬: 두 요소를 비교해 순서를 결정.
• 인플레이스 정렬: 추가 메모리 없이 배열 내에서 수행.
• 시간 복잡도: 최악과 평균의 경우 O(n²), 최선의 경우 O(n) (이미 정렬된 경우)
• 공간 복잡도: O(1) (추가적인 메모리 사용이 거의 없음)

1.3 특징

• 단순성: 코드가 직관적이고 구현이 쉬움.
• 안정 정렬(Stable Sort): 동일한 값을 가지는 원소들의 순서가 유지됨
• 비효율성: 데이터가 많아질수록 느려짐.

---

 

2. 버블 정렬 예시와 상세 설명

2.1 예시

입력 배열: [5, 3, 8, 4, 2]
결과: [2, 3, 4, 5, 8]

 

단계별 진행

1. 첫 번째 패스: [5, 3, 8, 4, 2] → [3, 5, 4, 2, 8]
   • 5와 3 비교(교환), 5와 8 비교(유지), 8과 4 비교(교환), 4와 2 비교(교환).
2. 두 번째 패스: [3, 5, 4, 2, 8] → [3, 4, 2, 5, 8]
   • 3과 5 비교(유지), 5와 4 비교(교환), 4와 2 비교(교환).
3. 세 번째 패스: [3, 4, 2, 5, 8] → [3, 2, 4, 5, 8]
   • 3과 4 비교(유지), 4와 2 비교(교환).
4. 네 번째 패스: [3, 2, 4, 5, 8] → [2, 3, 4, 5, 8]
   • 3과 2 비교(교환).

2.2 코드와 설명

public class BubbleSortExample {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {  // 패스 수
            for (int j = 0; j < n - i - 1; j++) {  // 비교 범위
                if (arr[j] > arr[j + 1]) {  // 인접 요소 비교
                    // 교환
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        System.out.print("정렬된 배열: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // 출력: 정렬된 배열: 2 3 4 5 8
    }
}

• 외부 루프(i): 정렬할 패스 수를 의미. 각 패스마다 끝부분이 정렬됨.
• 내부 루프(j): 비교와 교환을 수행. n-i-1까지 반복하는 이유는 이미 정렬된 마지막 i개는 제외하기 위함.
• 교환 로직: temp 변수를 사용해 두 요소를 스왑.

---

3. 코딩 테스트 문제와 풀이

코딩 테스트에서 버블 정렬은 구현 문제나 최적화 문제로 출제됩니다. 

3.1 문제 1: 기본 버블 정렬 구현

문제: 배열을 오름차순으로 정렬하시오.
입력: [64, 34, 25, 12, 22, 11, 90]
출력: [11, 12, 22, 25, 34, 64, 90]

 

풀이 방법

1. 두 개의 반복문 사용: 외부 루프는 패스, 내부 루프는 비교와 교환.
2. 인접 요소를 비교해 큰 값을 오른쪽으로 이동.

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

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.print("정렬된 배열: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // 출력: 정렬된 배열: 11 12 22 25 34 64 90
    }
}

• 시간 복잡도: O(n²), n=7이므로 최대 49번 비교.
• 공간 복잡도: O(1), 추가 배열 없이 수행.
• 동작 과정: 각 패스마다 가장 큰 값이 배열 끝으로 이동하며 정렬 범위가 줄어듦.

3.2 문제 2: 최적화된 버블 정렬 (조기 종료)

문제: 정렬이 완료되면 조기 종료하도록 버블 정렬을 수정하시오.
입력: [1, 2, 3, 5, 4]
출력: [1, 2, 3, 4, 5]

 

풀이 방법

1. 교환이 없으면 정렬이 끝났다고 판단하고 종료.
2. swapped 플래그로 교환 여부를 추적.

public class OptimizedBubbleSort {
    public static void optimizedBubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; 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 main(String[] args) {
        int[] arr = {1, 2, 3, 5, 4};
        optimizedBubbleSort(arr);
        System.out.print("정렬된 배열: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // 출력: 정렬된 배열: 1 2 3 4 5
    }
}

• 최선 시간 복잡도: O(n), 첫 패스에서 교환이 없으면 종료.
• 최악 시간 복잡도: O(n²), 모든 비교 필요.
• 장점: 거의 정렬된 배열에서 효율적. 예: 입력 배열은 두 번째 패스에서 종료.

---

4. 실무에서 버블 정렬 적용 사례

실무에서는 데이터 크기가 작을 때 버블 정렬을 활용할 수 있습니다.

• 네트워크 패킷 정렬: 소규모 패킷을 정렬할 때 사용
• UI 애니메이션 정렬: 간단한 시각적 정렬 효과 구현
• Java의 Comparator를 이용한 간단한 정렬 방식

4.1 예시: 사용자 이름 정렬

상황: 관리자 대시보드에서 최근 로그인한 5명의 사용자 이름을 정렬.

import org.springframework.stereotype.Service;
import java.util.List;

@Service
public class UserService {
    static class User {
        private String name;
        public User(String name) { this.name = name; }
        public String getName() { return name; }
        public void setName(String name) { this.name = name; }
    }

    public List<User> sortUsersByName(List<User> users) {
        int n = users.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (users.get(j).getName().compareTo(users.get(j + 1).getName()) > 0) {
                    User temp = users.get(j);
                    users.set(j, users.get(j + 1));
                    users.set(j + 1, temp);
                }
            }
        }
        return users;
    }

    public static void main(String[] args) {
        List<User> users = Arrays.asList(new User("Charlie"), new User("Alice"), new User("Bob"));
        UserService service = new UserService();
        service.sortUsersByName(users);
        users.forEach(user -> System.out.println(user.getName()));
        // 출력: Alice Bob Charlie
    }
}

 

• 적용 이유: 사용자 5명은 데이터가 작아 O(n²) 부담이 적음.
• Spring 통합: @Service로 서비스 레이어에서 사용 가능.

---

5. 장점과 단점

5.1 장점

• 구현 용이: 자바로 짧고 쉽게 작성 가능.
• 안정성: 동일 값의 순서 유지.
• 소규모 데이터: n이 작을 때 유용.
• 추가적인 메모리 사용이 거의 없음(O(1) 공간 복잡도)

5.2 단점

• 비효율성: 대규모 데이터에서 느림(O(n²)).
• 실무 제한: Arrays.sort() 같은 내장 함수가 더 빠름.
• 비교 횟수가 많아 연산량이 증가함
• 이미 정렬된 경우에도 기본 버전은 여전히 비교 연산을 수행

---

6. 결론

버블 정렬은 가장 단순한 정렬 알고리즘 중 하나로, 학습 목적으로는 훌륭하지만 실무에서 대규모 데이터를 처리하는 데에는 적합하지 않습니다. 하지만 작은 데이터셋을 정렬하거나 특정 애니메이션 효과를 만들 때 유용할 수 있습니다. 보다 효율적인 정렬이 필요한 경우 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 또는 힙 정렬(Heap Sort) 등을 고려하는 것이 좋습니다.