버블 정렬 (Bubble Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드, 주의점, 장단점

버블 정렬 총 정리

 

 

 

 

 

 

1. 버블 정렬이란?

버블 정렬은 인접한 두 요소를 비교하며 정렬하는 가장 기본적인 정렬 알고리즘입니다. 간단한 구조와 구현 덕분에 학습 목적으로 자주 사용되지만, 효율성 면에서는 다른 정렬 알고리즘에 비해 성능이 떨어집니다.

---

 

 

2. 원리

1. 첫 번째 요소와 두 번째 요소를 비교하여 크기를 기준으로 위치를 바꿉니다.
2. 두 번째 요소와 세 번째 요소를 비교하여 동일한 작업을 수행합니다.
3. 마지막 요소까지 이 작업을 반복합니다. 이 과정을 한 번 완료하면 가장 큰 값이 맨 끝에 위치하게 됩니다.
4. 위 과정을 반복하며 정렬되지 않은 나머지 요소를 계속 비교해 정렬을 완성합니다.

---

 

 

3. 동작 예시 (구체적인 설명)

정렬할 배열: [5, 3, 8, 4, 2], 오름차순으로 정렬하기

1. 첫 번째 패스 (Pass 1):
   • 비교: 5와 3 → 3과 5로 스왑 → [3, 5, 8, 4, 2]
   • 비교: 5와 8 → 스왑 없음 → [3, 5, 8, 4, 2]
   • 비교: 8과 4 → 4와 8로 스왑 → [3, 5, 4, 8, 2]
   • 비교: 8과 2 → 2와 8로 스왑 → [3, 5, 4, 2, 8]
   • 맨 끝 위치에 가장 큰 원소인 8이 위치하게 됨.
2. 두 번째 패스 (Pass 2):
   • 비교: 3과 5 → 스왑 없음 → [3, 5, 4, 2, 8]
   • 비교: 5와 4 → 4와 5로 스왑 → [3, 4, 5, 2, 8]
   • 비교: 5과 2 → 2와 5로 스왑 → [3, 4, 2, 5, 8]
   • 끝에서 두번째 위치에 두번째로 큰 원소인 5가 위치하게 됨.
3. 세 번째 패스 (Pass 3):
   • 비교: 3과 4 → 스왑 없음 → [3, 4, 2, 5, 8]
   • 비교: 4와 2 → 2와 4로 스왑 → [3, 2, 4, 5, 8]
4. 네 번째 패스 (Pass 4):
   • 비교: 3과 2 → 2와 3로 스왑 → [2, 3, 4, 5, 8]

최종 정렬 결과: [2, 3, 4, 5, 8]

---

 

 

4. 시간 복잡도

• 최선의 경우 (이미 정렬된 경우): O(n)
• 평균적인 경우: O(n²)
• 최악의 경우: O(n²)

반응형

---

 

 

5. 코드 예제

C 코드

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; 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;
            }
        }
    }
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, n);
    
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

 

 

Java 코드

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; 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);
        
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

 

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]

arr = [5, 3, 8, 4, 2]
bubble_sort(arr)
print(arr)

---

 

 

6. 주의점

1. 데이터가 많을수록 비효율적이기 때문에 작은 배열에서만 사용 권장.
2. 이미 정렬된 배열에서도 불필요한 비교가 발생할 수 있음. 이를 개선하려면 플래그 변수를 사용하여 추가 최적화를 고려.

---

 

 

7. 장단점

장점

• 간단하고 이해하기 쉬운 구조.
• 코드 작성이 쉽고, 초보자 학습에 적합.

단점

• 데이터가 많을수록 성능이 급격히 저하됨.
• 다른 효율적인 정렬 알고리즘에 비해 사용 빈도가 적음.

 

 

함께 보면 좋은 글

코딩 테스트에 나오는 거의 모든 정렬 알고리즘들에 대해 비교했습니다. 언제 어떤 정렬 알고리즘을 쓰면 좋은지에 대해서도 작성했습니다. 아래 링크에 자세히 작성했습니다.

 

2025.01.03 - [알고리즘] - 정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주요 특징, 상황에 따른 선택 기준

정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주