C++로 구현하는 재귀 버블 정렬 프로그램

버블 정렬(Bubble Sort)은 인접한 두 요소를 비교하여 순서가 잘못되어 있으면 서로 교환하는 방식으로 배열을 정렬하는 대표적인 알고리즘입니다. 일반적인 버블 정렬은 반복문을 사용하지만, 재귀 버블 정렬은 자기 자신을 다시 호출하는 재귀 함수를 활용한다는 점이 특징입니다.

재귀 버블 정렬의 동작 원리

재귀(자기 호출) 함수는 한 번의 호출에서 인접한 두 요소를 비교하고, 순서가 잘못되어 있으면 교환하는 작업을 수행합니다. 그런 다음 배열의 크기를 하나 줄여 스스로를 다시 호출하며, 이 과정이 배열 전체가 오름차순으로 정렬될 때까지 반복됩니다.

입출력 예시

입력: 53421
출력: 12345

C++ 코드 예제

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = { 5,4,2,1,3 };
    int n = 5;
    bubbleSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout<< arr[i]<<"\t";
    }
    return 0;
}

코드 설명

bubbleSort 함수는 먼저 for 루프를 통해 배열의 처음부터 끝까지 인접한 두 요소를 차례대로 비교합니다. 앞의 값이 뒤의 값보다 크면 임시 변수 temp를 사용해 두 값을 교환(swap)하여, 매 순회마다 가장 큰 값이 배열의 끝으로 이동하게 됩니다.

한 번의 순회가 끝나면 n - 1 > 1 조건을 검사합니다. 아직 정렬해야 할 요소가 남아 있다면 배열의 크기를 하나 줄인 상태로 bubbleSort를 재귀적으로 호출합니다. 이렇게 하면 이미 제자리에 놓인 마지막 요소는 더 이상 처리하지 않고, 나머지 부분에 대해서만 정렬이 계속 진행됩니다.

main 함수에서는 {5, 4, 2, 1, 3} 배열을 선언하고 bubbleSort를 호출한 뒤, 정렬된 결과를 탭 문자로 구분하여 출력합니다. 실행 결과는 1 2 3 4 5가 출력됩니다.

시간 및 공간 복잡도

재귀 버블 정렬의 시간 복잡도는 최악의 경우와 평균의 경우 모두 O(n²)이며, 이미 정렬된 배열인 최선의 경우에는 O(n)입니다. 또한 반복문 기반 버블 정렬과 달리 재귀 호출 스택이 사용되므로 공간 복잡도는 O(n)입니다.