정렬 알고리즘 (Sorting Algorithms) - 버블 정렬 (Bubble Sort)

버블 정렬(Bubble Sort)은 가장 단순한 정렬 알고리즘 중 하나입니다. 이름처럼 배열의 요소들이 "거품처럼" 위로 떠오르는 방식으로 정렬됩니다. 다음은 버블 정렬에 대한 자세한 설명입니다.

---

1. 정렬 방식

• 배열의 인접한 두 요소를 비교하여, 필요에 따라 위치를 교환합니다.
• 한 번의 반복(iteration) 후 가장 큰 값(또는 가장 작은 값)이 배열의 끝으로 이동합니다.
• 다음 반복에서는 정렬된 부분을 제외한 나머지 배열에서 같은 작업을 수행합니다.
• 이 과정을 반복하여 배열을 완전히 정렬합니다.

---

2. 특징

• 시간 복잡도:
  • 최악: O(n^2) (비효율적)
  • 최선: O(n) (이미 정렬된 경우, 단순 비교만 수행)
• 공간 복잡도: O(1)  (추가 메모리 사용 없음)
• 안정 정렬: 값이 같은 요소들의 상대적인 순서가 유지됩니다.
• 작은 데이터셋에서는 동작 원리가 직관적이라 배우기 쉽지만, 큰 데이터셋에서는 비효율적입니다.

---

3. 동작 원리

예시: 배열 [5, 3, 8, 4, 2]

1. 첫 번째 반복:
   • (5, 3): 5 > 3이므로 교환 → [3, 5, 8, 4, 2]
   • (5, 8): 5 < 8이므로 그대로 유지 → [3, 5, 8, 4, 2]
   • (8, 4): 8 > 4이므로 교환 → [3, 5, 4, 8, 2]
   • (8, 2): 8 > 2이므로 교환 → [3, 5, 4, 2, 8]
     가장 큰 값(8)이 맨 끝으로 이동.
2. 두 번째 반복:
   • (3, 5): 3 < 5이므로 그대로 유지 → [3, 5, 4, 2, 8]
   • (5, 4): 5 > 4이므로 교환 → [3, 4, 5, 2, 8]
   • (5, 2): 5 > 2이므로 교환 → [3, 4, 2, 5, 8]
     두 번째로 큰 값(5)이 제자리.
3. 세 번째 반복:
   • (3, 4): 3 < 4이므로 그대로 유지 → [3, 4, 2, 5, 8]
   • (4, 2): 4 > 2이므로 교환 → [3, 2, 4, 5, 8]
     세 번째로 큰 값(4)이 제자리.
4. 네 번째 반복:
   • (3, 2): 3 > 2이므로 교환 → [2, 3, 4, 5, 8]

반응형

4. Java 구현

다음은 Java로 구현된 버블 정렬 코드입니다.

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false; // 최적화를 위해 추가
            for (int j = 0; j < n - i - 1; 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;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original Array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        bubbleSort(arr);

        System.out.println("\nSorted Array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

5. Python 구현

다음은 Python으로 구현된 버블 정렬 코드입니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# 예제
print(bubble_sort([5, 1, 4, 2, 8]))  # [1, 2, 4, 5, 8]

 

---

6. 최적화

• 기본적으로 버블 정렬은 𝑛−1 번의 반복을 수행하지만, 배열이 이미 정렬된 경우에도 불필요하게 실행됩니다.
• 이를 개선하기 위해 스왑이 발생하지 않으면 반복을 종료하는 방식으로 최적화할 수 있습니다.

---

7. 장단점

장점:

• 구현이 매우 간단하고 직관적입니다.
• 추가 메모리를 사용하지 않으므로 공간 효율적입니다.

단점:

• 성능이 매우 떨어져 실제 사용은 거의 없습니다.
• 데이터의 크기가 커질수록 비효율적입니다.

버블 정렬은 학습 목적으로 적합하며, 실제 프로젝트에서는 더 효율적인 정렬 알고리즘(퀵 정렬, 병합 정렬 등)을 사용하는 것이 좋습니다.