버블 정렬(Bubble Sort)은 인접한 두 요소를 비교해 나가며 데이터를 정렬하는 가장 간단한 정렬 알고리즘 중 하나입니다. 모든 요소는 여러 단계(pass)에 걸쳐 비교되는데, 첫 번째 단계에서 가장 큰 값이 배열의 맨 끝으로 이동하고, 두 번째 단계에서 두 번째로 큰 요소가 뒤에서 두 번째 자리에 배치되는 식으로 전체 리스트가 정렬될 때까지 반복됩니다.
버블 정렬 알고리즘
int arr[5] = { 5, 4, 2, 1, 3 };
int i, j;
인덱스 i = 0부터 i < 배열 크기까지 순회합니다.
인덱스 j = 0부터 배열 크기 - i - 1까지 순회합니다.
arr[j] > arr[j + 1]이면 두 요소를 서로 교환(swap)합니다.
종료
재귀적 버블 정렬
배열 길이가 1이면 즉시 반환합니다. (종료 조건)
배열을 한 번 순회하면서 가장 큰 요소를 맨 끝에 고정합니다.
마지막 요소를 제외한 나머지 배열에 대해 위 과정을 재귀적으로 수행합니다.
예시
입력 − Arr[] = { 5, 7, 2, 3, 1, 4 }; length = 6
출력 − 정렬된 배열: 1 2 3 4 5 7
설명 −
첫 번째 패스
5 7 2 3 1 4 → swap → 5 2 7 3 1 4
5 2 7 3 1 4 → swap → 5 2 3 7 1 4
5 2 3 7 1 4 → swap → 5 2 3 1 7 4
5 2 3 1 7 4 → swap → 5 2 3 1 4 7
두 번째 패스
5 2 3 1 4 7 → swap → 2 5 3 1 4 7
2 5 3 1 4 7 → swap → 2 3 5 1 4 7
2 3 5 1 4 7 → swap → 2 3 1 5 4 7
2 3 1 5 4 7 → swap → 2 3 1 4 5 7
세 번째 패스
2 3 1 4 5 7 → swap → 2 1 3 4 5 7
2 1 3 4 5 7 교환 없음
네 번째 패스
2 1 3 4 5 7 → swap → 1 2 3 4 5 7
1 2 3 4 5 7 이후 반복에서는 더 이상 교환이 일어나지 않음
입력 − Arr[] = { 1, 2, 3, 3, 2 };
출력 − 정렬된 배열: 1 2 2 3 3
설명 −
첫 번째 패스
1 2 3 3 2 → swap → 1 2 3 2 3
1 2 3 2 3 → swap → 1 2 2 3 3
1 2 2 3 3 이후 반복에서는 교환 없음
두 번째 패스
1 2 2 3 3 이후 반복에서는 교환 없음
프로그램의 접근 방식
재귀적 버블 정렬에서 종료 조건(base case)은 배열 길이가 1인 경우입니다. 그 외의 경우에는 하나의 for 루프만으로 배열을 순회하며 필요할 때마다 인접 요소를 교환한 뒤, 남은 부분 배열에 대해 스스로를 다시 호출하는 방식으로 동작합니다.
입력 배열 Arr[]와 요소 개수인 length를 받습니다.
함수 recurbublSort(int arr[], int len)는 배열과 그 길이를 인자로 받아 버블 정렬을 재귀적으로 수행하여 배열을 정렬합니다.
교환용 임시 변수 temp를 준비합니다.
배열 길이가 1이면 아무 작업 없이(void) 반환합니다.
그렇지 않으면 하나의 for 루프로 배열을 순회하면서, 각 위치에서 arr[i] > arr[i + 1]이면 두 요소를 교환합니다.
temp = arr[i], arr[i] = arr[i + 1], arr[i + 1] = temp 순서로 값을 치환합니다.
방금 수행한 루프에서 가장 큰 요소가 이미 마지막 위치에 놓였으므로 length를 1 감소시킵니다.
recurbublSort(arr, len)을 재귀 호출합니다.
모든 호출이 끝나 len이 1이 되면 재귀를 빠져나오며, 이때 배열은 완전히 정렬된 상태가 됩니다.
main 함수 내에서 정렬된 배열을 출력합니다.
예제 코드
#include <stdio.h>
void recurbublSort(int arr[], int len){
int temp;
if (len == 1){
return;
}
for (int i=0; i<len-1; i++){
if (arr[i] > arr[i+1]){
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
len=len-1;
recurbublSort(arr, len);
}
int main(){
int Arr[] = {21, 34, 20, 31, 78, 43, 66};
int length = sizeof(Arr)/sizeof(Arr[0]);
recurbublSort(Arr, length);
printf("Sorted array : ");
for(int i=0;i<length;i++){
printf("%d ",Arr[i]);
}
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Sorted array: 20 21 31 34 43 66 78
마무리: 시간 복잡도와 활용 팁
재귀적 버블 정렬은 반복문 기반 버블 정렬과 마찬가지로 평균 및 최악의 경우 시간 복잡도가 O(n²)입니다. 또한 함수 호출마다 스택 프레임이 쌓이므로 O(n) 크기의 추가 스택 공간이 필요하다는 점을 유의해야 합니다. 재귀 개념을 익히는 학습용 예제로는 매우 적합하지만, 실제 대용량 데이터를 정렬할 때는 퀵 정렬이나 병합 정렬처럼 O(n log n)의 성능을 보이는 알고리즘을 사용하는 것이 좋습니다.