#2 버블 정렬(Bubble sort)

일단 한번 눈앞이 보이기 시작하면, 다시 맹인인 척을 할 수는 없다. - 스베틀라나 이오시포브나 알릴루예나

 

버블 정렬에 대해 정렬한다. 아마도... O(n²) 시간복잡도를 가지는 정렬들 중에서는 제일 유명하다고 생각.

 

일단 그냥 텍스트로 설명하자면, 1번째와 2번째 원소를 비교하여 정렬하고(그러니까 둘을 비교해서 순서를 정리한다는 말이다), 2번째와 3번째, 그리고 N-1번째와 N번째를 정렬한 뒤 처음으로 돌아가서 n-2번째와 n-1번째까지 해서... 최대 n(n-1)/2번 정렬하는 알고리즘.

 

당연하게도 일반적으로 최악의 성능을 자랑하지만, 그만큼 구현 난이도는 쉽다. 전형적인 코테용 알고리즘이라고 보면 된다. 누가 대체 데이터량의 제곱을 처리하는 알고리즘을 쓰겠어...

 

void bubbleSort(int arr[], int n) {
    bool swapped; // 교환시 실제로 진행되었는지 확인하는 플래그
    for (int i = 0; i < n; i++) {
        swapped = false; // 초기에는 교환이 없다고 가정
        for (int j = 0; j < n - i - 1; j++) { // / 현재 스캔 중인 부분에서 가장 큰 요소를 맨 끝으로 보내므로 n - i - 1까지만 반복. 게시글에서 더 자세하게 설명
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped)
            break;
    }
}

 

버블 정렬의 예제 코드. 딱 봐도 비효율적이지 않는가?

여기서 n은 받을 배열의 크기고, arr[]은 받을 매개변수 배열.

 

조금 파보면 곧바로 이해하기는 쉬우나, 이 부분이 살짝 이해가 가지 않을 수 있다.

 

for (int j = 0; j < n - i - 1; j++)

 

여기서 j는 현재 스캔 중인 부분의 인덱스를 나타내고, n - i - 1은 현재 단계에서 비교해야 하는 요소의 개수를 나타낸다. 각 단계별로 이미 가장 큰 요소들이 배열의 뒤쪽으로 이동하고 정렬되었기 때문에, 다음 단계에서는 이 요소들은 더 이상 비교할 필요가 없어서 이런 식으로 코드를 작성하는 것.

 

예를 들어보자면... 배열의 길이가 7이고 현재 i가 0일 때, 내부 루프는 다음과 같이 동작한다.

• j는 0부터 5까지 반복 (n - 0 - 1 = 6).
• 이 때, 가장 큰 요소는 인덱스 6에 있으며, 인덱스 6과는 더 이상 비교하지 않아도 된다.

즉, 내부 루프는 현재 단계에서 가장 큰 요소를 배열의 끝에 정렬하므로, 불필요한 비교를 줄일 수 있는 것이다.

 

int main() {
    int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; // 정렬할 배열
    int n = sizeof(arr) / sizeof(arr[0]); // 배열의 크기

    std::cout << "정렬 전: ";
    for (int i = 0; i < n; ++i)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    bubbleSort(arr, n); // 버블 정렬 호출

    std::cout << "정렬 후: ";
    for (int i = 0; i < n; ++i)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    return 0;
}

 

이제 직접 테스트해보자. 

 

 

정상적으로 출력되는 것을 확인 가능.

이제 병합 정렬에 대해서 알아볼 시간이다.