재귀 삽입 정렬이란?
삽입 정렬(Insertion Sort)은 배열을 '정렬된 부분'과 '정렬되지 않은 부분'으로 나눈 뒤, 정렬되지 않은 요소를 하나씩 꺼내 올바른 위치에 삽입하는 방식의 정렬 알고리즘입니다. 일반적으로 반복문으로 구현하지만, 재귀 호출을 활용하면 코드가 더 간결해지고 재귀적 사고방식을 익히는 좋은 연습 예제가 됩니다.
예제 코드
다음은 Java로 작성한 재귀 삽입 정렬 프로그램입니다.
import java.util.Arrays;
public class Demo{
static void recursive_ins_sort(int my_arr[], int arr_len){
if (arr_len <= 1)
return;
recursive_ins_sort(my_arr, arr_len-1);
int last = my_arr[arr_len-1];
int j = arr_len-2;
while (j >= 0 && my_arr[j] > last){
my_arr[j+1] = my_arr[j];
j--;
}
my_arr[j+1] = last;
}
public static void main(String[] args){
int my_arr[] = {11, 23, 67, 83, 42, 11, 0};
recursive_ins_sort(my_arr, my_arr.length);
System.out.println("삽입 정렬 수행 후 배열의 요소는 다음과 같습니다.");
System.out.println(Arrays.toString(my_arr));
}
}실행 결과
삽입 정렬 수행 후 배열의 요소는 다음과 같습니다. [0, 11, 11, 23, 42, 67, 83]
코드 동작 원리
Demo 클래스 안에는 정적(static) 재귀 함수 recursive_ins_sort가 정의되어 있으며, 이 함수는 배열과 배열의 길이를 매개변수로 받습니다. 동작 과정은 다음과 같습니다.
1. 기저 조건(Base Case) 확인
배열의 길이가 1 이하라면 이미 정렬된 상태로 간주하고 아무 작업 없이 그대로 반환합니다. 이것이 재귀 호출을 멈추는 기저 조건입니다.
2. 재귀 호출로 앞부분 정렬
배열 길이를 하나씩 줄여가며 자기 자신을 다시 호출합니다. 이렇게 하면 가장 작은 크기의 문제부터 차례대로 해결되며, 결국 전체 배열이 정렬됩니다.
3. 마지막 요소를 올바른 위치에 삽입
정렬된 앞부분에 현재 부분 배열의 마지막 요소(last)를 삽입해야 합니다. 인덱스 변수 j를 사용해 앞쪽 요소들을 하나씩 비교하면서, last보다 큰 요소를 만나면 해당 요소를 한 칸씩 뒤로 밀어냅니다. 그런 다음 빈 자리에 last를 넣으면 해당 요소가 제 위치에 놓이게 됩니다.
4. 결과 출력
main 메서드에서는 초기 배열 {11, 23, 67, 83, 42, 11, 0}을 대상으로 정렬을 수행한 뒤, Arrays.toString()을 사용해 정렬된 결과를 콘솔에 출력합니다.
참고: 시간 복잡도와 주의 사항
재귀 삽입 정렬의 시간 복잡도는 최악의 경우(역순으로 정렬된 배열) O(n²), 이미 정렬된 배열에서는 O(n)입니다. 또한 재귀 호출 깊이가 배열 길이만큼 늘어나므로, 배열이 매우 클 경우 스택 오버플로(stack overflow)가 발생할 수 있다는 점을 유의해야 합니다. 따라서 실무에서는 대용량 데이터에 대해 반복문 기반 구현이나 더 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다.