거품 정렬 (Bubble Sort) 이란?

 

 

 

 

 

 

 

 

 

 

거품 정렬(Bubble Sort)은 간단하고 직관적인 정렬 알고리즘으로, 인접한 두 원소를 비교하여 순서가 잘못된 경우 교환하며 정렬을 수행합니다. 이 과정은 리스트가 완전히 정렬될 때까지 반복됩니다.

 

알고리즘 동작 원리

1. 리스트의 처음부터 끝까지 인접한 두 원소를 비교합니다.
2. 두 원소의 순서가 올바르지 않다면 서로 교환합니다.
3. 첫 번째 단계가 끝나면 가장 큰 값이 리스트의 마지막 위치로 이동합니다.
4. 위 과정을 리스트 크기 - 1 만큼 반복합니다.

이 알고리즘은 리스트의 크기에 따라 비교 및 교환을 반복하여 정렬을 완료합니다.

 

예제

정렬되지 않은 리스트

[5, 3, 8, 4, 2]

단계별 동작

1단계 (첫 번째 루프)

• 5와 3을 비교: 교환
  • [3, 5, 8, 4, 2]
• 5와 8을 비교: 교환하지 않음
  • [3, 5, 8, 4, 2]
• 8과 4를 비교: 교환
  • [3, 5, 4, 8, 2]
• 8과 2를 비교: 교환
  • [3, 5, 4, 2, 8]

2단계 (두 번째 루프)

• 3과 5를 비교: 교환하지 않음
  • [3, 5, 4, 2, 8]
• 5와 4를 비교: 교환
  • [3, 4, 5, 2, 8]
• 5와 2를 비교: 교환
  • [3, 4, 2, 5, 8]

3단계 (세 번째 루프)

• 3과 4를 비교: 교환하지 않음
  • [3, 4, 2, 5, 8]
• 4와 2를 비교: 교환
  • [3, 2, 4, 5, 8]

4단계 (네 번째 루프)

• 3과 2를 비교: 교환
  • [2, 3, 4, 5, 8]

정렬 완료!

정렬된 리스트

[2, 3, 4, 5, 8]

 

시간 복잡도

최선의 경우 (이미 정렬된 경우)

• 비교만 수행하고 교환은 발생하지 않음.
• O(n)

최악의 경우 (역순 정렬된 경우)

• 모든 요소가 교환되어야 함.
• O(n^2)

평균의 경우

• 요소들이 무작위로 섞여 있는 경우.
• O(n^2)

 

공간 복잡도

• 추가적인 메모리를 사용하지 않으므로 O(1).

 

장점

1. 구현이 간단하다.
2. 데이터가 거의 정렬되어 있는 경우 효율적이다.

단점

1. 비효율적: 큰 데이터셋에서 성능이 떨어진다.
2. O(n^2)의 시간 복잡도로 인해 다른 정렬 알고리즘보다 느리다.

 

개선된 거품 정렬 (Optimized Bubble Sort)

만약 특정 단계에서 교환이 발생하지 않았다면, 리스트가 이미 정렬된 상태임을 알 수 있습니다. 이를 통해 불필요한 반복을 줄일 수 있습니다.

개선된 알고리즘

public static void optimizedBubbleSort(int[] arr) {
    boolean swapped;
    for (int i = 0; i < arr.length - 1; i++) {
        swapped = false;
        for (int j = 0; j < arr.length - 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;
    }
}

 

 

 

 

거품 정렬은 학습 목적으로 유용하지만, 실제로는 데이터 크기가 작거나 거의 정렬된 경우에만 사용됩니다. 데이터 크기가 클 경우에는 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort)과 같은 효율적인 알고리즘을 사용하는 것이 좋습니다.