정렬 - 버블정렬(Bubble Sort)

버블정렬(Bubble Sort)

 

이전에 알아본 선택정렬 다음은 버블정렬입니다. 버블 정렬을 간단하게 요약하면 "옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법" 입니다.

 

#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(arr[j], arr[j + 1]);
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Before sorting: ";
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    cout << "After sorting: ";
    printArray(arr, n);
    
    return 0;
}

 

위 소스코드는 C++로 짜여진 1~10까지의 숫자를 오름차순으로 정렬시키는 버블정렬입니다. 위 소스코드에서 printArray함수와 main함수는 그다지 중요하지 않고, 위에 BubbleSort함수를 살펴보면 됩니다. 위 함수는 2중 for문과 if문, 그리고 C++의 내장함수인 swap을 통해 구현하였습니다.

 

버블정렬의 동작과정을 간단하게 살펴보겠습니다.

 

1. 배열의 첫번째와 두번째 원소를 비교합니다.

2. 첫번째 원소가 두번쨰 원소보다 크면 두 원소의 자리를 바꿉니다.

3. 다음으로 두번째와 세번째 원소를 비교합니다. 같은 방식으로 필요하면 자리를 바꿉니다.

4. 이 과정을 배열의 끝까지 반복합니다.

5. 한 번의 전체 순회가 끝나면 가장 큰 값이 배열의 맨 끝으로 이동합니다.

6. 이 과정을 다시 첫 번째 원소부터 반복합니다. 이미 정렬된 값들은 제외하고, 나머지 값들을 같은 방식으로 비교합니다.

7. 더 이상 교환이 일어나지 않을 때까지 반복합니다.

 

이제 간단한 예시를 들어 보겠습니다.

[5, 3, 8, 4, 2]가 있을 때 오름차순으로 버블정렬을 하면 5와 3을 비교하여 교환해 [3, 5, 8, 4, 2]가 되고, 이후 5와 8을 비교하여 교환하지 않습니다. 이런식으로 배열의 끝까지 순서대로 순회를 마치면 첫번째 순회가 끝나고, 숫자는 [3, 5, 4, 2, 8]이 됩니다. 이 상태는 아직 정렬이 끝나지 않았기 때문에 두번째 순회를 진행합니다. 같은 방식으로 비교하며 순회를 하되, 위 동작과정에서 볼 수 있듯이 한 번의 순회가 끝나면 가장 큰 값이 배열의 맨 끝으로 이동하기 때문에 마지막 값은 더 이상 비교할 필요가 없습니다. 이런 식으로 모든 순회를 끝마치면 최종적으로 [2, 3, 4, 5, 8]이 나오게 됩니다.

 

버블정렬의 특징

시간복잡도 : O(n^2)

=> 최악의 경우(배열이 완전히 역순으로 정렬된 경우-각 원소마다 비교/교환) : O(n^2), 최선의 경우(배열이 이미 정렬된 경우-한번의 순회로 정렬 확인) : O(n), 평균 시간복잡도 : O(n^2)

=> 일반적으로 버블정렬의 성능은 최악과 크게 다르지 않으며, 평균적으로도 O(n^2)의 시간복잡도를 갖습니다.

공간복잡도 : O(1)

=> 버블정렬은 제자리 정렬로 별도의 추가 메모리 공간을 거의 사용하지 않습니다.

안정성 : 안정 정렬

=> 같은 값을 가진 요소들의 순서는 정렬 후에도 유지됩니다.

 

장단점

장점

- 간단한 구현 : 이해하고 구현하기 쉬운 알고리즘입니다.

- 적은 데이터에 적합 : 데이터가 적거나 이미 거의 정렬된 경우 성능이 나쁘지 않습니다.

- 안정 정렬 : 같은 값을 가지는 원소들의 순서가 유지됩니다.

 

단점

- 비효율적 : 데이터의 양이 많을 경우 시간복잡도가 O(n^2)이기 때문에 다른 알고리즘에 비해 성능이 매우 떨어집니다.

- 실제 응용에서 잘 사용되지 않음 : 교육 목적으로는 자주 사용되나, 효율성이 떨어져 실제로는 거의 사용되지 않습니다.

 

버블정렬의 활용

버블정렬은 작은 크기의 데이터를 처리하거나, 추가 메모리 사용이 불가능한 환경에서 유리할 수 있습니다. 또한, 안정정렬이 필요한 경우나 알고리즘 학습 목적으로도 적합합니다. 그러나 데이터 양이 많아지거나, 정렬 상태와 관계없이 항상 성능이 좋은 알고리즘을 요구하는 경우에는 퀵 정렬, 병합정렬 등 더 효율적인 정렬 알고리즘을 사용하는 것이 일반적으로 더 좋습니다.

 

버블정렬은 실시간 정렬 필요시 유용할 수 있습니다. 실시간으로 새로운 데이터가 계속 들어오는 경우, 버블 정렬을 사용하면 데이터를 지속적으로 정렬 상태로 유지할 수 있습니다. 리스트의 맨 뒤에 새 데이터를 추가한 뒤, 새로운 데이터를 앞의 원소들과 비교하여 적절한 위치에 삽입할 수 있습니다. 이는 비효율적일 수 있지만, 매우 작은 데이터에서 실시간으로 추가적인 데이터를 정렬해야 할 때 유용할 수 있습니다.

 

개선된 버블정렬

기본 버블정렬은 이미 정렬된 상태에서도 모든 요소를 비교하고, 총 n-1번의 순회를 수행하는데 이는 매우 비효율적입니다.

예를 들어, [1, 2, 3, 4, 5]에 기본 버블 정렬을 적용하면 교환은 일어나지 않지만, 불필요한 비교작업을 총 4번 수행합니다.

 

개선된 버블정렬은 한 번의 순회에서 교환이 발생하지 않으면 리스트가 정렬된 상태라고 판단하고, 더 이상 순회를 수행하지 않습니다.(조기종료) 이로 인해 최선의 경우 시간복잡도는 O(n)이 됩니다. 또한, 각 순회마다 가장 큰 값이 뒤로 이동하므로, 이미 정렬된 구간은 더 이상 비교하지 않습니다. 

예를 들어, [1, 2, 3, 4, 5]에 개선된 버블 정렬을 적용하면 첫 순회에서 교환이 발생하지 않으므로 더 이상 반복하지 않고 정렬이 완료됩니다.

 

NEXT

오늘은 두번째 정렬, 버블 정렬에 대해서 알아보았습니다. 다음에는 삽입정렬을 알아보도록 하겠습니다. 감사합니다.