Bubble Sort 버블 정렬

버블 정렬(Bubble Sort) - 단순하지만 효율적이지 않은 정렬 알고리즘

버블 정렬이란?

728x90

버블 정렬은 가장 기본적이고 직관적인 정렬 알고리즘 중 하나입니다. 배열의 인접한 두 원소를 비교하여 순서대로 정렬되어 있지 않으면 서로 위치를 교환하는 방식으로 동작합니다. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다.

버블 정렬의 작동 원리

1. 배열의 첫 번째 원소와 두 번째 원소를 비교하여 순서대로 정렬되어 있지 않으면 서로 위치를 교환합니다.
2. 이 과정을 배열의 마지막 원소까지 반복합니다.
3. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다.
4. 마지막 원소부터 차례대로 정렬이 완료되어, 가장 큰 원소가 배열의 끝으로 이동합니다.

반응형

버블 정렬의 장단점

장점:

• 구현이 매우 단순하여 이해하기 쉽습니다.
• 코드가 간결하고 직관적이어서 프로그래밍을 배우는 초보자들에게 유용합니다.

단점:

• 시간 복잡도가 평균 및 최악의 경우 모두 O(n^2)로, 배열의 크기가 커질수록 성능이 급격히 저하됩니다.
• 거품처럼 서서히 정렬되는 과정이 비효율적이므로, 실제 성능이 중요한 애플리케이션에서는 더 효율적인 정렬 알고리즘을 사용해야 합니다.

따라서 버블 정렬은 단순성과 직관성이 장점이지만, 성능 측면에서는 다른 정렬 알고리즘에 비해 효율적이지 않습니다. 프로그래밍 입문자들에게는 좋은 학습 도구가 될 수 있지만, 실제 애플리케이션에서는 더 우수한 정렬 알고리즘을 사용하는 것이 좋습니다.

 

<Python 예제 코드>

def bubble_sort(arr):
    n = len(arr)

    # 배열의 길이만큼 반복
    for i in range(n):
        # 배열의 끝에서 i 번째 원소까지 비교
        for j in range(0, n - i - 1):
            # 인접한 두 원소 비교
            if arr[j] > arr[j + 1]:
                # 순서가 바르지 않으면 swap
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# 사용 예시
arr = [64, 34, 25, 12, 22, 11, 90]
print("Original array:", arr)

bubble_sort(arr)

print("Sorted array:", arr)

SMALL

<C++ 예제 코드>

#include <iostream>
using namespace std;

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]) {
                // 인접한 두 원소 swap
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    bubbleSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

 

 

버블 정렬의 시간 복잡도

 

버블 정렬은 평균 및 최악의 경우 모두 O(n^2)의 시간 복잡도를 가집니다. 이는 배열의 크기가 커질수록 성능이 급격히 저하된다는 것을 의미합니다.

1. 최선의 경우(Best Case): 배열이 이미 정렬되어 있는 경우, 최선의 경우 시간 복잡도는 O(n)입니다. 이 경우 단 한 번의 반복으로 정렬이 완료되기 때문입니다.
2. 평균 경우(Average Case): 배열의 원소가 무작위로 분포되어 있는 경우, 평균 시간 복잡도는 O(n^2)입니다. 이는 배열의 크기가 커질수록 성능이 급격히 저하된다는 것을 의미합니다.
3. 최악의 경우(Worst Case): 배열이 역순으로 정렬되어 있는 경우, 최악의 경우 시간 복잡도도 O(n^2)입니다. 이 경우 모든 인접한 원소를 비교하고 교환해야 하기 때문입니다.

따라서 버블 정렬은 배열의 크기가 크거나 정렬이 필요한 데이터의 양이 많은 경우에는 비효율적일 수 있습니다.

이러한 경우에는 퀵 정렬, 병합 정렬 등과 같은 더 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다.

 

버블 정렬의 단순성과 직관성은 장점이지만, 시간 복잡도 측면에서의 단점은 고려해야 할 중요한 요소입니다.

알고리즘의 성능 특성을 이해하고 문제 상황에 맞는 최적의 알고리즘을 선택하는 것이 중요합니다.