[알고리즘] 버블 정렬 ( Bubble Sort )

버블정렬

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

인접한 두원소를 비교하고, 그 순서가 잘못되어있으면 두 원소를 교환하는 과정을 반복하여 전체 리스트를 정렬하는 방법

 

버블 정렬은 제자리 정렬( in-place sorting) 알고리즘으로, 추가적인 메모리 공간을 거의 사용하지않음

---

버블 정렬 동작 원리

리스트를 반복적으로 순회하며, 각 순회에서 인접한 두원소를 비교하여 교환

이과정을 거치면서 가장 크거나 가장작은 원소가 리스트의 끝으로 이동하게 됩니다.

다음 순회에서는 그이전에 정렬된 원소를 제외하고 다시 비교/교환을 수행

 

---

예 )   초기 배열 [ 5, 3, 8, 4, 2]

첫번째 순회

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 ]

 

두번째 순회

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]

 

 

 

세번째 순회

3과 4를 비교: 3 < 4이므로 교환 없음 → [3, 4, 2, 5, 8]

4와 2를 비교: 4 > 2이므로 교환         → [3, 2, 4, 5, 8]

 

네번째 순회

3과 2를 비교: 3 > 2이므로 교환 → [2, 3, 4, 5, 8]

 

---

버블 정렬 구현 ( Java )

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

        // 배열의 크기만큼 반복
        for (int i = 0; i < n - 1; i++) {
            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 = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));  // [2, 3, 4, 5, 8]
    }
}

코드 설명

swapped 플래그 : 각 패스에서 원소들이 교환되었는지를 기록

교환이 발생하지 않았다면 이미 리스트는 정렬된 상태이니 반복을 중지

 

내부 루프( n - i - 1 ) : 이미 정렬된 마지막 부분을 제외하고 비교/교환을 수행

---

버블 정렬의 시간 복잡도

(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2 이므로 O(n^2) 입니다.

하지만 버블 정렬은 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에

최선, 평균, 최악의 경우 모두 시간 복잡도는 O(n^2) 으로 동일

 

 

최선의 경우: O(n) – 배열이 이미 정렬된 경우

 

평균의 경우: O(n^2)

 

최악의 경우: O(n^2)

 

---

버블 정렬의 공간 복잡도

주어진 배열안에서 교환 ( swap )을 통해서 정렬이 동작되기때문에 O(n) 이다.

---

버블 정렬의 장단점

장점

구현이 간단: 버블 정렬은 이해하고 구현하기 매우 쉬운 알고리즘입니다.

 

추가 메모리 필요 없음: 제자리 정렬 알고리즘이기 때문에 추가적인 메모리 공간이 필요하지 않음.

 

이미 정렬된 경우 매우 효율적: 만약 데이터가 이미 정렬되어 있다면 O(n)의 시간 복잡도로 동작.

---

단점

비효율적: 평균 및 최악의 경우 시간 복잡도가 O(n^2)이므로 큰 데이터 세트를 처리하는 데 적합하지 않음.

 

교환 횟수 많음: 다른 정렬 알고리즘에 비해 원소 교환이 빈번하게 일어나기 때문에 성능이 떨어짐.

---

버블 정렬이 사용되는 경우

버블 정렬은 일반적으로 학습 목적으로 많이 사용됩니다.

실무에서는 다른 고급 정렬알고리즘을 사용하지만, 간단한 문제를 해결하거나

정렬 알고리즘의 기본 개념을 익히고자할때 버블 정렬을 사용합니다. 또한

코드가 매우 간단하여 정렬이 필요하지만 성능이 크게 중요하지 않는 경우에도 사용 될수 있음.