알고리즘 개념 설명

버블 정렬(Bubble Sort)은 인접한 두 요소를 비교하여 필요 시 교환하는 방식으로 작동하는 간단한 정렬 기법입니다. 배열 내에서 가장 큰 값이 거품(bubble)처럼 점차 끝으로 밀려나가기 때문에 이 이름이 붙었습니다.

n개의 원소로 구성된 배열을 정렬한다고 가정할 때, 첫 번째 패스에서는 처음부터 끝까지 인접한 원소들을 비교하며 더 큰 값을 오른쪽으로 이동시킵니다. 이를 통해 가장 큰 값이 배열의 마지막 위치에 도달하게 됩니다. 다음 패스에서는 마지막 원소를 제외한 나머지 부분에 대해 동일한 작업을 수행합니다. 이 과정을 반복하면 전체 배열이 오름차순으로 정렬됩니다.

시간 복잡도 분석

버블 정렬은 중첩 반복문을 사용하므로 최악 및 평균 시간 복잡도는 O(n²)입니다. 입력 데이터가 이미 정렬되어 있는 경우 최선의 상황이 발생하지만, 기본적인 구현에서는 여전히 전체 순회를 수행하기 때문에 개선된 버전이 아니라면 성능 향상은 미미합니다.

구현 방법

재귀적 방식

void bubbleSortRecursive(int arr[], int length) {
    if (length <= 1) return;

    for (int i = 0; i < length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }

    bubbleSortRecursive(arr, length - 1);
}

이 방식은 매번 배열의 유효 길이를 하나씩 줄이며 재귀 호출을 통해 정렬을 진행합니다.

반복적 방식 (기본형)

void bubbleSortIterative(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;
            }
        }
    }
}

외부 루프는 정렬 단계를 제어하고, 내부 루프는 인접 원소 간 비교 및 교환을 수행합니다. 매 반복 후 가장 큰 원소가 올바른 위치에 자리하게 됩니다.

비효율적 변형 (비추천)

void selectionLikeBubble(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

이 코드는 버블 정렬보다 선택 정렬(Selection Sort)과 유사한 로직을 따르며, 실제 인접 요소 간 비교라는 버블 정렬의 본질과 다릅니다.

완전한 테스트 가능한 코드 예제

#include <iostream>
using namespace std;

void swapElements(int* x, int* y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

void bubbleSort(int data[], int size) {
    if (size <= 1) return;

    for (int i = 0; i < size - 1; i++) {
        if (data[i] > data[i + 1]) {
            swapElements(&data[i], &data[i + 1]);
        }
    }

    bubbleSort(data, size - 1);
}

int main() {
    const int MAX_SIZE = 1000;
    int inputArray[MAX_SIZE];
    int count;

    cin >> count;

    for (int i = 0; i < count; i++) {
        cin >> inputArray[i];
    }

    bubbleSort(inputArray, count);

    for (int i = 0; i < count; i++) {
        cout << inputArray[i] << " ";
    }
    cout << endl;

    return 0;
}

테스트 결과 검증

임의의 500개 숫자를 입력으로 제공했을 때, 프로그램은 이를 오름차순으로 정확히 정렬하여 출력합니다. 또한 이미 정렬된 1~500까지의 수열을 입력으로 주었을 때도 동일한 결과를 안정적으로 유지합니다.