버블 정렬

버블 정렬은 인접한 요소를 반복해서 비교하고 오름차순에 어긋난 요소의 위치를 바꾸는 비교 기반 정렬 알고리즘입니다. 한 번의 전체 순회가 끝나면 정렬되지 않은 부분에서 가장 큰 값이 오른쪽의 최종 위치로 이동합니다. 목록을 따라 값이 반복해서 이동하는 모습에서 이런 이름이 붙었습니다. 버블 정렬은 과정을 추적하고 구현하기 쉽지만, 실행 시간이 제곱에 비례하므로 큰 데이터 모음에는 적합하지 않습니다.

버블 정렬 알고리즘

n개의 요소가 있는 배열 A에서 A[0]과 A[1]을 비교한 다음, A[1]과 A[2]를 비교하는 식으로 정렬되지 않은 부분을 따라 비교합니다. 왼쪽 값이 오른쪽 값보다 크면 두 값을 바꿉니다. 이 조건은 오름차순으로 정렬하며, 내림차순으로 정렬하려면 비교 조건을 반대로 바꾸면 됩니다.

한 번의 패스는 왼쪽에서 오른쪽으로 한 차례 훑는 과정입니다. 패스가 끝나면 방문한 부분의 가장 큰 값이 오른쪽 경계에 놓이므로 다음 패스는 한 칸 앞에서 멈출 수 있습니다. 첫 패스에서는 n - 1쌍을 비교하고, 다음 패스에서는 n - 2쌍을 비교하는 식으로 줄어듭니다. 고정 패스 구현은 n - 1번 패스를 수행하며, 마지막 패스에서도 비교할 쌍이 하나 남습니다. 요소가 두 개보다 적은 목록은 비교할 필요가 없습니다.

버블 정렬 알고리즘 예제

입력이 (5, 3, 4, 2, 1)이라고 가정해 보겠습니다. 첫 번째 패스에서는 인접한 쌍을 차례로 비교합니다. 5와 3을 바꾸면 (3, 5, 4, 2, 1)이 됩니다. 5와 4를 바꾸면 (3, 4, 5, 2, 1)이 되고, 5와 2를 바꾸면 (3, 4, 2, 5, 1)이 됩니다. 마지막으로 5와 1을 바꾸면 (3, 4, 2, 1, 5)가 됩니다. 이제 가장 큰 값이 오른쪽에 자리 잡았습니다.

두 번째 패스는 앞의 네 값만 살펴보고 (3, 2, 1, 4, 5)를 만듭니다. 세 번째 패스에서는 정렬되지 않은 앞부분이 (2, 1, 3, 4, 5)로 바뀌고, 네 번째 패스가 끝나면 (1, 2, 3, 4, 5)가 됩니다. 이 과정은 패스마다 경계가 줄어들고, 이미 제자리를 찾은 값은 다시 비교하지 않는 이유를 보여 줍니다.

C++로 버블 정렬 구현하기

이 완전한 프로그램은 예제의 값을 제자리에서 정렬합니다. 내부 반복문의 범위인 n - i - 1은 이미 정렬된 끝부분을 다시 비교하지 않도록 합니다. values[j] > values[j + 1] 조건은 순서가 잘못된 인접한 쌍을 교환해 작은 값이 왼쪽으로 이동하게 합니다.

예제를 실행해 보세요.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

#include <iostream>
#include <utility>
#include <vector>

void bubble_sort(std::vector<int>& values) {
    const int n = static_cast<int>(values.size());
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (values[j] > values[j + 1]) {
                std::swap(values[j], values[j + 1]);
            }
        }
    }
}

int main() {
    std::vector<int> values{5, 3, 4, 2, 1};
    bubble_sort(values);
    std::cout << "Sorted:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
}

Sorted: 1 2 3 4 5

제공된 실행 결과에 따르면 프로그램은 성공적으로 완료되어 정렬된 값을 출력했습니다. 변경되지 않는 예제 출력에는 Sorted: 레이블이 영어로 표시됩니다.

버블 정렬의 복잡도와 한계

고정 패스 구현은 입력 순서와 관계없이 (n - 1) + (n - 2) + ... + 1, 즉 n(n - 1) / 2번 비교합니다. 따라서 최선, 평균, 최악의 시간 복잡도는 모두 O(n²)입니다. 역순으로 정렬된 입력과 같은 최악의 경우에는 교환도 많이 발생합니다. 이 구현은 벡터를 직접 수정하고 교환할 때 임시 값 하나만 사용하므로 보조 공간 복잡도는 O(1)입니다.

조기 종료 방식은 패스 중 교환이 있었는지 기록하고, 값이 바뀌지 않은 패스가 끝나면 정렬을 멈출 수 있습니다. 이 방식은 이미 정렬된 입력에서 O(n) 시간이 걸리지만, 평균과 최악의 경우는 여전히 O(n²)입니다. 위의 고정 패스 코드는 이 최적화를 포함하지 않습니다. 버블 정렬은 인접한 값의 비교를 배우거나 아주 작은 입력을 정렬할 때 유용하지만, 큰 데이터 모음에는 일반적으로 표준 라이브러리의 정렬 알고리즘이 더 적합합니다.