버블 정렬(Bubble Sort)은 가장 널리 알려진 정렬 알고리즘 중 하나로, 보통 반복문을 이용한 순차적(iterative) 방식으로 구현됩니다. 하지만 이번 글에서는 재귀(recursion)를 활용한 버블 정렬 구현 방법을 살펴보겠습니다.
재귀 방식의 핵심 아이디어는 간단합니다. 한 번의 패스(pass)를 통해 배열의 가장 큰 원소를 맨 뒤로 보낸 뒤, 정렬이 완료된 마지막 원소를 제외하고 나머지 부분 배열에 대해 자기 자신을 다시 호출하는 것입니다.
알고리즘
bubbleRec(arr, n)
begin
if n = 1, return
for i in range 1 to n-2, do
if arr[i] > arr[i+1], then
exchange arr[i] and arr[i+1]
end if
done
bubbleRec(arr, n-1)
end알고리즘의 동작 과정을 단계별로 설명하면 다음과 같습니다.
- 종료 조건: 배열 크기 n이 1이면 더 이상 정렬할 원소가 없으므로 재귀를 종료합니다.
- 한 번의 패스: 인접한 두 원소를 비교하여 앞의 값이 더 크면 서로 교환(swap)합니다. 이 과정이 끝나면 가장 큰 값이 배열 끝에 위치하게 됩니다.
- 재귀 호출: 마지막 원소를 제외한 n-1개의 원소에 대해 bubbleRec을 다시 호출합니다.
C++ 구현 예제
#include<iostream>
using namespace std;
void recBubble(int arr[], int n){
if (n == 1)
return;
for (int i=0; i<n-1; i++) // 각 패스마다 인접 원소 비교
if (arr[i] > arr[i+1]) // 현재 원소가 다음 원소보다 크면
swap(arr[i], arr[i+1]); // 두 원소를 교환
recBubble(arr, n-1); // 정렬된 마지막 원소를 제외하고 재귀 호출
}
main() {
int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
int n = sizeof(data)/sizeof(data[0]);
cout << "Sorted Sequence ";
recBubble(data, n);
for(int i = 0; i<n;i++){
cout << data[i] << " ";
}
}실행 결과
Sorted Sequence 13 20 32 35 40 54 74 98 98 154
코드 설명
위 코드에서 recBubble 함수는 먼저 종료 조건(n == 1)을 확인한 후, for 반복문으로 현재 범위 내에서 인접한 원소들을 비교·교환하며 한 번의 패스를 수행합니다. 패스가 끝나면 n-1을 인자로 넘겨 스스로를 다시 호출함으로써 점점 작은 부분 배열을 정렬해 나갑니다.
시간 복잡도
재귀 버블 정렬의 시간 복잡도는 일반적인 버블 정렬과 동일합니다. 최악 및 평균의 경우 O(n²), 이미 정렬된 배열에 대한 최선의 경우 O(n)입니다. 다만 재귀 호출마다 스택 프레임이 쌓이므로 공간 복잡도는 O(n)이 되며, 깊은 재귀가 발생할 경우 스택 오버플로우 위험도 고려해야 합니다.