버블 정렬(Bubble Sort)은 인접한 두 요소를 반복적으로 비교하고 교환하며 배열을 정렬하는 가장 기본적인 알고리즘 중 하나입니다. 일반적으로 반복문으로 구현하지만, 재귀(Recursion)를 활용하면 더 간결하게 표현할 수 있습니다.
재귀 버블 정렬의 동작 원리
재귀 버블 정렬은 한 번의 패스(pass)마다 가장 큰 요소를 배열 끝으로 밀어낸 뒤, 남은 구간에 대해 자기 자신을 다시 호출하는 방식으로 동작합니다. 정렬해야 할 범위가 점점 줄어들고, 길이가 1이 되면 더 이상 정렬할 필요가 없으므로 재귀가 종료됩니다.
예제 코드
import java.util.Arrays;
public class Demo{
static void bubble_sort(int my_arr[], int len_arr){
if (len_arr == 1)
return;
for (int i=0; i<len_arr-1; i++)
if (my_arr[i] > my_arr[i+1]){
int temp = my_arr[i];
my_arr[i] = my_arr[i+1];
my_arr[i+1] = temp;
}
bubble_sort(my_arr, len_arr-1);
}
public static void main(String[] args){
int my_arr[] = {45, 67, 89, 31, 63, 0, 21, 12};
bubble_sort(my_arr, my_arr.length);
System.out.println("The array after implementing bubble sort is ");
System.out.println(Arrays.toString(my_arr));
}
}실행 결과
The array after implementing bubble sort is [0, 12, 21, 31, 45, 63, 67, 89]
코드 설명
'Demo' 클래스 안에는 버블 정렬을 수행하는 bubble_sort 메서드가 정의되어 있습니다. 먼저 매개변수로 전달받은 배열 길이(len_arr)가 1이라면 더 이상 비교할 요소가 없으므로 그대로 반환하여 재귀를 종료합니다.
그렇지 않은 경우, 배열을 처음부터 순회하면서 현재 위치의 요소가 바로 다음 위치의 요소보다 크면 두 요소의 값을 서로 교환(swap)합니다. 이 과정에서 임시 변수 temp를 사용해 값을 안전하게 치환합니다.
첫 번째 패스가 완료되면 가장 큰 요소가 배열의 마지막 위치에 고정됩니다. 이후에는 해당 요소를 제외한 나머지 부분에 대해 bubble_sort를 재귀적으로 호출하여 정렬 범위를 하나씩 줄여 나갑니다.
main 메서드에서는 정렬할 배열 {45, 67, 89, 31, 63, 0, 21, 12}을 선언하고, 이를 버블 정렬 함수의 인자로 전달합니다. 정렬이 완료되면 Arrays.toString()을 통해 결과를 출력합니다. 실행 결과를 보면 배열이 [0, 12, 21, 31, 45, 63, 67, 89]로 오름차순 정렬된 것을 확인할 수 있습니다.
참고로 버블 정렬의 시간 복잡도는 최악 및 평균의 경우 O(n²)이며, 공간 복잡도는 제자리(in-place) 정렬 방식이므로 O(1)입니다. 학습용으로 적합하지만, 대용량 데이터에는 퀵 정렬이나 병합 정렬 같은 효율적인 알고리즘을 사용하는 것이 좋습니다.