Bubble Sort (버블 정렬)

 

버블 정렬이란?

버블 정렬(Bubble Sort)은 대표적인 간단한 정렬 알고리즘 중 하나이다. 인접한 두 원소를 서로 비교하여 크기 순서대로 자리를 교환하는 방식을 반복하여 전체 데이터를 정렬한다. 이때 각 반복 과정을 거치며 큰 원소가 마치 "거품(Bubble)"이 수면 위로 떠오르듯 배열의 끝 부분으로 이동하는 모습 때문에 ‘버블 정렬’이라는 이름이 붙었다.

버블 정렬의 기본 원리는 다음과 같다.

1. 배열의 첫 번째 원소부터 시작하여 바로 옆 원소와 크기를 비교한다.
2. 만약 두 원소가 잘못된 순서(예: 오름차순일 때 앞 원소가 더 클 경우)에 있다면, 두 원소의 자리를 서로 바꾼다.
3. 배열의 끝까지 1~2단계를 반복하면, 가장 큰 값이 배열의 맨 끝으로 이동한다.
4. 위 과정을 배열의 길이만큼 반복하면 모든 원소가 정렬된 상태가 된다.

이러한 과정을 통해 버블 정렬은 직관적이고 쉽게 구현할 수 있는 알고리즘으로 알려져 있다.

---

버블 정렬 알고리즘 단계별 예시

버블 정렬이 어떻게 동작하는지 숫자 배열을 예로 들어서 살펴보자.

다음과 같은 배열이 있다고 가정한다.

[5, 3, 4, 1, 2]

 

이 배열을 오름차순으로 버블 정렬하는 과정을 단계별로 확인해보자.

 

1회차 순회

(5, 3) → [3, 5, 4, 1, 2]  // 자리 교환 (5 > 3)
(5, 4) → [3, 4, 5, 1, 2]  // 자리 교환 (5 > 4)
(5, 1) → [3, 4, 1, 5, 2]  // 자리 교환 (5 > 1)
(5, 2) → [3, 4, 1, 2, 5]  // 자리 교환 (5 > 2)
// 첫 번째 순회 결과: 가장 큰 숫자 5가 맨 끝으로 이동 완료

2회차 순회

(3, 4) → [3, 4, 1, 2, 5]  // 교환 필요 없음
(4, 1) → [3, 1, 4, 2, 5]  // 자리 교환 (4 > 1)
(4, 2) → [3, 1, 2, 4, 5]  // 자리 교환 (4 > 2)
// 두 번째 순회 결과: 두 번째 큰 숫자 4가 끝에서 두 번째로 이동 완료

3회차 순회

(3, 1) → [1, 3, 2, 4, 5]  // 자리 교환 (3 > 1)
(3, 2) → [1, 2, 3, 4, 5]  // 자리 교환 (3 > 2)
// 세 번째 순회 결과: 세 번째 큰 숫자 3의 자리 확정

4회차 순회

(1, 2) → [1, 2, 3, 4, 5]  // 교환 필요 없음
// 네 번째 순회 결과: 모든 숫자의 위치 확정

이 과정을 통해 최종적으로 배열은 다음과 같이 정렬된 상태가 된다.

[1, 2, 3, 4, 5]

버블 정렬의 핵심은 이처럼 매 순회마다 가장 큰 값이 배열의 끝으로 이동하여 위치를 확정짓는 것이다.

---

버블 정렬의 시간 복잡도 및 공간 복잡도 분석

버블 정렬의 성능은 배열의 상태에 따라 달라질 수 있다. 성능을 평가하기 위해 최선의 경우(Best Case), 평균적인 경우(Average Case), 최악의 경우(Worst Case)의 세 가지 상황을 나누어 시간 복잡도를 분석할 수 있다.

시간 복잡도

• 최선의 경우 (Best Case): ⟨⟨O(n)⟩⟩
  • 이미 배열이 완벽하게 정렬된 상태라면 한 번의 순회만으로 정렬 완료 여부를 확인할 수 있기 때문에 시간 복잡도는 ⟨⟨O(n)⟩⟩이 된다.
• 평균적인 경우 (Average Case): ⟨⟨O(n²)⟩⟩
  • 일반적으로 배열이 무작위로 섞여 있다면 모든 원소를 여러 번 순회해야 하므로 시간 복잡도는 ⟨⟨O(n²)⟩⟩이 된다.
• 최악의 경우 (Worst Case): ⟨⟨O(n²)⟩⟩
  • 배열이 완벽히 역순으로 정렬된 경우에는 매번 교환 작업이 일어나므로 시간 복잡도는 ⟨⟨O(n²)⟩⟩으로 가장 나쁘다.

이처럼 버블 정렬의 평균 및 최악의 성능이 ⟨⟨O(n²)⟩⟩으로 매우 느리기 때문에, 데이터가 많아지면 실무에서는 거의 사용하지 않는다.

공간 복잡도

버블 정렬은 주어진 배열 내부에서 원소를 교환하여 정렬하기 때문에 추가적인 배열이나 자료구조가 필요하지 않다. 따라서 공간 복잡도는 ⟨⟨O(1)⟩⟩이다.

---

버블 정렬의 장단점과 사용처

버블 정렬은 간단하고 직관적인 정렬 알고리즘이지만, 효율성 문제로 인해 실제 사용이 제한적인 편이다. 장단점과 적합한 사용처를 알아보자.

 

버블 정렬의 장점

• 간단한 구현: 알고리즘이 매우 직관적이고 이해하기 쉬워 초보자 교육이나 간단한 예제로 적합하다.
• 추가 공간 불필요: 원본 배열 내에서 교환(swap) 작업만 이루어지므로 추가 메모리가 거의 필요 없다. (공간 복잡도 ⟨⟨O(1)⟩⟩)
• 정렬 여부 확인 용이: 이미 정렬된 배열에 대해 빠르게 정렬 여부를 확인할 수 있는 최적화가 가능하다.

버블 정렬의 단점

• 낮은 효율성: 평균 및 최악의 시간 복잡도가 ⟨⟨O(n²)⟩⟩이기 때문에 데이터의 크기가 커지면 성능이 급격히 저하된다.
• 실제 환경에서 제한적인 활용도: 실제 프로그램에서는 대부분 버블 정렬보다 빠른 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 팀 정렬(Tim Sort) 등의 알고리즘이 선호된다.

버블 정렬의 적합한 사용처

• 학습 목적 및 예제: 정렬 알고리즘 학습 및 프로그래밍 기초 교육 시 유용하다.
• 작은 데이터 정렬: 데이터 개수가 매우 적을 경우(예: 수십 개 이하의 데이터) 간단히 구현하고 사용할 수 있다.
• 정렬 여부 검증: 이미 정렬된 상태인지 빠르게 확인할 때 효율적인 최적화를 활용하면 유용하다.

이처럼 버블 정렬은 실무보다는 주로 학습 및 간단한 데이터 처리 목적에 적합하다.

---

버블 정렬 최적화 방법

버블 정렬의 기본적인 구현은 불필요한 반복 작업이 많아 비효율적이다. 이 단점을 조금이나마 보완하기 위한 최적화 방법이 존재한다.

 

최적화 전략

• 매 순회마다 이미 정렬된 구간을 탐지하여 불필요한 작업을 생략하는 방식이다.
• 한 번의 전체 순회 과정 중 교환 작업이 단 한 번도 발생하지 않았다면 이미 정렬이 완료된 상태이므로 즉시 정렬을 종료할 수 있다.

최적화된 버블 정렬 예시

예를 들어 다음과 같은 배열이 있다고 하자.

[1, 2, 3, 4, 5]

이 배열은 이미 정렬된 상태이다. 기존의 버블 정렬은 이런 경우에도 모든 요소를 여러 번 순회하지만, 최적화된 버블 정렬은 다음과 같이 한 번의 순회 후 즉시 종료된다.

 

1회차 순회:

(1, 2) 교환 없음
(2, 3) 교환 없음
(3, 4) 교환 없음
(4, 5) 교환 없음
// 교환이 전혀 없었으므로 즉시 정렬 종료

이러한 최적화를 통해 버블 정렬의 최선 시간 복잡도를 ⟨⟨O(n)⟩⟩으로 낮출 수 있다.

 

최적화된 버블 정렬 Java 코드 예시

public void optimizedBubbleSort(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]) {
                // 교환(swap)
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true; // 교환 발생 시 플래그 설정
            }
        }
        
        if (!swapped) break; // 교환이 없으면 정렬 완료로 판단 후 종료
    }
}

이처럼 최적화를 적용하면 특정 상황에서는 버블 정렬의 성능이 크게 향상될 수 있다.

---

Java 코드로 구현한 버블 정렬 예제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BubbleSort {

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

        for (int i = 0; i < size - 1; i++) {
            swapped = false;
            for (int j = 0; j < size - 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 main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int[] arr = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }
        System.out.println("정렬 전 : " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("정렬 후 : " + Arrays.toString(arr));
    }
}